짧은 일정

요즘은 누구나 클라우드 컴퓨팅에 관심이 많아서, 상당히 다양한 사업 모델이 실험되고 있다. 당신은 매우 간단한 모델을 시도하고 있다. 즉, 슬롯이라고 부르는 두 종류의 묶음 중 하나로 기계의 사용 시간을 판매한다. 고객은 $Q$이 어떤 정수일 때, CPU 시간의 일 초 또는 $Q$초를 구매할 수 있다.

고객이 구매한 각 시간 슬롯은 하나의 기계에서 전부 처리되어야 하지만, 구매된 시간 슬롯을 기계들에 어떻게 배분할지는 당신이 결정할 수 있다.

긴 휴가를 마치고 돌아와 보니, 모든 기계가 유휴 상태이고 다양한 주문이 들어와 있다. 고객을 만족시키려면, 구매된 시간 슬롯이 마침내 모두 완료되는 시각을 최소화하도록 이 요청들을 기계들에 배분하는 방법을 결정해야 한다.

구매된 모든 시간 슬롯을 완료할 수 있는 최소 시간은 얼마인가?

입력은 네 정수 $Q$ ($2 \leq Q \leq 1\,000$), $M$ ($1 \leq M \leq 1\,000\,000$), $S$ ($0 \leq S \leq 1\,000\,000$), $L$ ($0 \leq L \leq 1\,000\,000$)가 포함된 한 줄로 이루어진다. 각각 더 긴 묶음을 완료하는 데 필요한 시간, 회사가 보유한 기계의 수, 구매된 1초 시간 슬롯의 수, 구매된 $Q$초 시간 슬롯의 수를 나타낸다.

구매된 모든 시간 슬롯을 완료할 수 있는 최소 시간을 출력한다.