Informatica Online Judge

  우유 [1227 / 04CB]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 23   Total Tried : 29


The Champion of this Problem (C++) : gs15120 - 0ms / 1216byte
My Best Submission (C++) : N/A

[USACO 2005 March Gold]

Background

지용이는 재현이한테 생일 선물로 우유 공장을 선물해줬다.

하지만 애석하게도 재현이는 유당불내증이 있어서 이걸로 장사를 할 계획이다.

재현이는 이후 N주동안 우유를 생산하려고 한다. 우유를 생산하는데 드는 비용은 그때그때 다르기 때문에, i번째 주에 우유 1L를 생산하는 데 드는 비용 Ci가 주어진다. i번째 주에 생산할 수 있는 우유의 양은 무한하다.

또한, 지용이는 재현이를 위해서 창고 역시 선물해 줬다. 창고는 1주에 1L의 우유를 저장하는 데 S의 비용이 들며, 생물을 잘하는 지용이는 창고 안에 있는 우유가 썩지 않음을 보장할 수 있다. 또한, 창고의 크기 역시 무한하다.

재현이는 N주동안 GSHS에서의 우유 수요량 Yi를 모두 조사했다. 어떻게 해야지 총 비용을 최소로 하면서 수요를 모두 만족시킬 수 있을까?

Input

첫째 줄에 N과 S가 주어진다.
이후 N개의 줄에 Ci, Yi가 주어진다.

[입력값의 정의역]
1 <= N <= 10,000
1 <= S <= 100
1 <= Ci <= 5,000
0 <= Yi <= 10,000

Output

재현이가 주어진 수요를 만족하기 위해 들여야 하는 비용의 최솟값을 출력한다. long long 형을 사용해야 함에 유의하라.

IO Example

입력
4 5
88 200
89 400
97 300
91 500

출력
126900

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]