요플레 공장 > 문제은행



2194 : 요플레 공장

제한시간
1000 ms   
메모리제한
32 MB   
해결횟수
822 회   
시도횟수
2581 회   

문제

요플레 공장을 운영하시는 영휘의 아버지가 어머니와 함께 여행을 가신다. 

그래서 영휘는 아버지를 대신해서 요플레 공장을 N주 동안 운영해야한다.

 

영휘가 걱정스러운 아버지는 영휘를 위해 N주 동안 필요한 우유의 양과 변동되는 가격을 미리 알아봐주었다.

 

아버지가 주신 정보에 의하면 각 주마다 우유는 1ℓ당 C원에 살 수 있고, 필요한 우유는 Yℓ이다. 

또한 우유를 1주일 보관하는데 우유 1ℓ당 S원의 비용이 든다. 

우유는 N주 동안 보관이 가능하며 우유 창고가 굉장히 커서 우유를 얼마든지 보관이 가능하다.

 

영휘는 아버지에게 칭찬을 받기 위해 N주 동안 최소의 비용으로 요플레 공장을 운영하고 싶어서 당신에게 도움을 청했다.

 

당신은 영휘에게 N주 동안 요플레 공장을 운영할 수 있는 최소비용을 구하여 주자.


입력형식

첫 줄에 N과 S (1≤N≤10,000, 1≤S≤100)가 공백으로 구분되어 주어진다.

둘째 줄 부터 N+1번째 줄 까지 각 주의 C[i]와 Y[i] (1≤C[i]≤5,000, 0≤Y[i]≤10,000)가 주어진다. 

각 주는 1주부터 순서대로 입력이 된다.


출력형식

N주 동안 요플레 공장을 운영할 수 있는 최소비용을 출력한다.

입력 예

4 5
88 200
89 400
97 300
91 500

출력 예

126900

그리디

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010-2019 jungol. All right reserved.

TOP