요플레 공장

요플레 공장을 운영하시는 영휘의 아버지가 어머니와 함께 여행을 가신다. 그래서 영휘는 아버지를 대신해서 요플레 공장을 N주 동안 운영해야한다.

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

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

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

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

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

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

입력

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

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

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

출력

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

예제1

힌트

출처

USACO March 2005 Silver 1번, Gold 3번

요플레 공장 1초 32MB