요구르트 공장

면접 대비

시간 제한1초메모리 제한1024 MB

요약

주마다 생산 비용과 배송량, 그리고 단위당 주간 보관료가 주어질 때 모든 주의 배송을 맞추는 최소 총비용을 구합니다.

난이도: 보통10점 중 5점
유형: 그리디, 동적 계획법
정답자: 아직 제출이 없습니다

문제

회사는 세계적으로 유명한 Yucky Yogurt를 만드는 요구르트 공장을 인수했다. 앞으로 $N$ ( $1 \le N \le 10,000$ )주 동안 우유와 인건비 가격이 매주 변동하여, $i$ 주차에 요구르트 한 개를 생산하는 데 드는 비용은 $C_i$ 센트 ( $1 \le C_i \le 5,000$ )이다. 이 공장은 설계가 잘 되어 있어서 매주 얼마든지 많은 양을 생산할 수 있다.

이 회사는 창고를 갖고 있다. 창고에 쌓아 둔 요구르트는 한 단위당 주마다 $S$ 센트 ( $1 \le S \le 100$ )의 일정한 보관료가 든다. 요구르트는 상하지 않는다. 창고는 매우 커서 얼마든지 많은 양을 보관할 수 있다.

Yucky는 고객에게 매주 $Y_i$ ( $0 \le Y_i \le 10,000$ )단위의 요구르트를 배송하려 한다. 여기서 $Y_i$ 는 $i$ 주차의 배송량이다. $N$ 주 동안의 총비용을 최소화하는 방법을 찾아라. $i$ 주차에 생산한 요구르트와 이미 창고에 있던 요구르트는 모두 그 주의 수요를 맞추는 데 쓸 수 있다.

입력

첫 줄에 공백으로 구분된 두 정수 $N$ 과 $S$ 가 주어진다.

$i+1$ 번째 줄 ( $1 \le i \le N$ )에는 공백으로 구분된 두 정수 $C_i$ 와 $Y_i$ 가 주어진다.

출력

첫 줄에 요구르트 배송 계획을 만족시키는 최소 총비용을 정수 하나로 출력한다. 총비용은 32비트 정수 범위를 넘을 수 있다.

힌트

1주차에는 200단위를 생산해 전부 배송한다. 2주차에는 700단위를 생산하여 400단위를 배송하고, 300단위는 창고에 보관한다. 3주차에는 보관해 둔 300단위를 배송한다. 4주차에는 500단위를 생산해 모두 배송한다.

예제1

예제 1
입력
```
4 5
88 200
89 400
97 300
91 500
```
예상 출력
```
126900
```