Problemas
컴퓨터 전문 제작 업체인 (주)정올에서는 특별 행사 기간을 맞이하여, 특정 수량만큼 고객이 원하는 컴퓨터를 주문 제작해주고 있다. 즉, 컴퓨터 한 대에 필요한 부품들과 각 부품들이 만들어지는 순서, 그리고 컴퓨터 수량을 말해주면, 공장에서는 각 부품들이 만들어지는 시간들과 각 작업들의 제작을 고려하여 최소의 시간에 모든 컴퓨터를 공급해 줘야한다.
공장은 작업별로 분담을 하기 때문에, 하나의 작업 단계가 끝나서 부품이 만들어지면 다음 단계의 작업에서는 그 부품들을 이용하여 해당 작업만을 마친 후, 다시 다음 단계로 넘겨줘야 한다. 하지만 자신이 분담한 작업이 아무리 빨리 만들어진다고 해서 전체 완성품이 빨리 만들어지는 것은 아니다. 아래 <표1>을 살펴보면 작업 A와 작업 B가 완성되어야 작업 C를 시작 할 수 있다. 따라서 작업 A가 아무리 빨리 끝나도 B의 작업시간이 오래 걸리면 C는 B의 제작이 끝난 후에야 작업이 가능하다.
이렇게 작업을 할 때 생산시간을 단축시키기 위해서는 모든 부품을 일단 빨리 만들어 놓아야 한다. 예를 들어, <표1>과 같은 형태의 컴퓨터 3대를 만든다고 할 때 <표2>와 같이 1대를 만들 때는 10분이 소요되지만 두 번째는 5분, 세 번째도 5분이 걸려서 총 20분이 소요된다. 위와 같이 컴퓨터를 제작하는데 필요한 작업 순서와 각 제작의 소요 시간, 물건의 수량이 입력으로 들어올 때, 모든 물건이 완성되는데 걸리는 최소 시간을 출력하시오.
Entrada
첫 번째 줄에는 작업의 수 N(1≤N≤20) 과 작업 순서를 표현하는 데 필요한 줄 수, 그리고 컴퓨터의 수량 M(1≤M≤30)이 순서대로 입력된다. 다음 줄에는 각 작업의 이름과 각 작업을 하는데 필요한 시간이 입력된다.
작업의 이름은 'A'부터 알파벳 순서대로 차례로 부여한다. 작업을 수행하는데 필요한 수행 시간은 분 단위이며 1이상 60이하의 정수로 한다. 또한 완성단계에서의 제작 시간은 0이다. 그 다음 줄에는 완성품이 되기까지의 작업순서가 한 줄에 하나씩 입력된다. 작업 순서는 '먼저해야할 작업 다음에 해야 할 작업' 의 순서로 한 줄에 한 쌍씩 들어온다.
Salida
모든 컴퓨터가 생산되는데 걸리는 최소 시간을 출력한다.
Ejemplo
5 4 3
A 4
B 5
C 3
D 6
E 2
A C
B C
C E
D E
20
Debes iniciar sesión para escribir código.