공주의 결혼

어느 가난한 나라의 말괄량이 용감한 공주는 도박의 배당이 파리뮤추얼 방식으로 결정된다는 사실을 알게 되면서 도박에 대해 잘 알게 된 기분이 들어 도박에서 이길 것을 확신했다. 그 결과 평소보다 더 많은 돈을 쏟아부었고, 국민이 낸 세금을 전부 잃을 만큼 크게 졌다. 이 사태를 무겁게 받아들인 왕은 공주를 이웃 나라로 시집보내기로 했다. 공주가 평소 행실을 반성하게 하고, 동시에 이웃 나라와 교류를 깊여 재정 원조를 받으려는 생각이었다.

공주와 이웃 나라의 왕자는 서로 마음에 들었고, 두 나라 왕 사이에서도 정략결혼에 대한 동의가 이루어졌다. 공주는 얼마 안 되는 돈을 들고 의기양양하게 이웃 나라로 떠났다. 한편 공주가 시집가는 동기는 왕의 일방적인 이익 추구 때문이라며 못마땅하게 여긴 이웃 나라 왕자의 측근은 공주를 죽이기 위해 길 도중에 수많은 자객을 풀었다.

공주가 지나는 길은 이미 정해져 있다. 공주가 지나는 길에는 합계 L개의 숙박지가 있다. 편의상 출발 지점과 도착 지점도 숙박지로 두고, 각 숙박지를 S1, S2, ... SL이라 부르자. 공주는 처음에 S1에 있으며, 오름차순으로 (S2, S3 ... 순서로) 숙박지를 방문해 최종적으로 SL로 간다. 숙박지에서는 돈을 내고 호위를 고용할 수 있으며, 돈이 있는 한 원하는 거리만큼 계약해 공주를 지키게 할 수 있다. 호위를 고용하는 비용은 거리 1당 금 1이다. 공주는 지나는 구간 안을 부분적으로만 지켜지게 할 수도 있다. Si와 Si+1 사이의 거리는 Di, Si와 Si+1 사이에서 거리 1당 자객에게 습격당하는 횟수의 기댓값은 Pi로 주어진다.

공주가 예산 M을 가지고 있고, 자객에게 습격당하는 횟수의 기댓값이 최소가 되도록 호위를 고용했을 때, 목적지까지 자객에게 습격당하는 횟수의 기댓값을 구하라.

입력은 여러 데이터 세트로 이루어진다. 각 데이터 세트는 다음과 같은 형식을 따른다.

N M
D1 P1
D2 P2
...
DN PN

각 데이터 세트의 첫 줄에는 두 정수가 주어지며, 각각 구간의 수 N(1≤N≤10,000)과 공주가 가진 예산 M(0≤M≤1,000,000,000)을 나타낸다. 다음 N줄은 공주가 지나는 길의 정보를 나타낸다. 각 줄은 두 정수를 포함하며, i번째 줄은 구간의 거리 Di(1≤Di≤10,000)와 그 구간을 1단위 거리 이동할 때 습격당하는 횟수의 기댓값 Pi(0≤Pi≤10)로 이루어진다. 입력의 끝은 N=0, M=0인 데이터 세트로 나타낸다. 이 데이터 세트에 대해서는 계산 결과를 출력해서는 안 된다.

각 데이터 세트마다 공주가 목적지까지 자객에게 습격당하는 횟수의 기댓값을 출력하라.