작은 스케줄
면접 대비시간 제한1초메모리 제한512 MB
M개의 동일한 기계와 길이 1인 작업 S개, 길이 Q인 작업 L개가 있을 때 모든 작업을 끝내는 최소 완료 시간을 구한다.
문제
요즘은 모두 클라우드 컴퓨팅에 관심이 많아서 여러 가지 비즈니스 모델이 실험되고 있다. 당신은 아주 단순한 모델 하나를 시도하고 있다. 기계의 시간을 슬롯이라 부르는 두 종류의 묶음으로 판매하는 것이다. 고객은 CPU 시간 1초를 살 수도 있고, 어떤 정수 에 대해 초를 살 수도 있다.
고객이 구매한 각 시간 슬롯은 반드시 한 대의 기계에서 완료되어야 하지만, 구매한 시간 슬롯을 기계들 사이에 어떻게 배분할지는 당신이 정한다.
긴 휴가에서 돌아와 보니 모든 기계가 유휴 상태이고 여러 주문이 들어와 있다. 고객을 만족시키려면 이 요청들을 기계들 사이에 분배하여, 구매한 시간 슬롯이 전부 완료되는 시각을 최소화해야 한다.
구매한 시간 슬롯을 전부 완료할 수 있는 가장 짧은 시간은 얼마인가?
입력
입력은 네 정수 (), (), (), ()를 담은 한 줄로 이루어진다. 는 더 긴 묶음을 완료하는 데 필요한 시간, 은 회사가 보유한 기계의 수, 는 구매된 1초 시간 슬롯의 수, 은 구매된 초 시간 슬롯의 수이다.
출력
구매한 시간 슬롯을 전부 완료할 수 있는 가장 짧은 시간을 출력한다.