컴퓨터 전문 제작 업체인 (주)정올에서는 특별 행사 기간을 맞이하여, 특정 수량만큼 고객이 원하는 컴퓨터를 주문 제작해주고 있다. 즉, 컴퓨터 한 대에 필요한 부품들과 각 부품들이 만들어지는 순서, 그리고 컴퓨터 수량을 말해주면, 공장에서는 각 부품들이 만들어지는 시간들과 각 작업들의 제작을 고려하여 최소의 시간에 모든 컴퓨터를 공급해 줘야한다.

공장은 작업별로 분담을 하기 때문에, 하나의 작업 단계가 끝나서 부품이 만들어지면 다음 단계의 작업에서는 그 부품들을 이용하여 해당 작업만을 마친 후, 다시 다음 단계로 넘겨줘야 한다. 하지만 자신이 분담한 작업이 아무리 빨리 만들어진다고 해서 전체 완성품이 빨리 만들어지는 것은 아니다. 아래 <표1>을 살펴보면 작업 A와 작업 B가 완성되어야 작업 C를 시작 할 수 있다. 따라서 작업 A가 아무리 빨리 끝나도 B의 작업시간이 오래 걸리면 C는 B의 제작이 끝난 후에야 작업이 가능하다.

이렇게 작업을 할 때 생산시간을 단축시키기 위해서는 모든 부품을 일단 빨리 만들어 놓아야 한다. 예를 들어, <표1>과 같은 형태의 컴퓨터 3대를 만든다고 할 때 <표2>와 같이 1대를 만들 때는 10분이 소요되지만 두 번째는 5분, 세 번째도 5분이 걸려서 총 20분이 소요된다. 위와 같이 컴퓨터를 제작하는데 필요한 작업 순서와 각 제작의 소요 시간, 물건의 수량이 입력으로 들어올 때, 모든 물건이 완성되는데 걸리는 최소 시간을 출력하시오.

#1253 upload 15 done 7 how_to_reg 6

컴퓨터공장 timer 1s memory - MB

#1253

컴퓨터공장 1s - MB