요플레 공장

요플레 공장을 운영하시는 영휘의 아버지가 어머니와 함께 여행을 가신다. 그래서 영휘는 아버지를 대신해서 요플레 공장을 $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번

이 문제집에 아직 아무것도 없어요.