Princess' Marriage

お姫様の嫁入り

English text is not available in this practice contest.

ある貧乏な国のおてんばで勇敢なお姫様は，ギャンブルの配当がパリミュチュエル方式で決定される事を知ることにより，ギャンブルについて詳しくなった気がしてギャンブルでの勝利を確信した．その結果，今までよりも更に多額のお金をつぎ込み，国民が納めた税金をすべて失うほどの負けを喫してしまった．この事態を重く受け止めた王様は，お姫様を隣の国へ嫁がせることにした．こうすることにより，お姫様を日頃の行いを反省させ，同時に隣国との交友を深めて財政援助をしてもらおうと考えたからである．

お姫様と隣国の王子様はお互いの事が気に入り，また両国の王様間でも政略結婚に関する同意がなされた．お姫様はなけなしのお金を手に意気揚々と隣の国へ出かけた．一方で，お姫様が嫁ぐ動機は王様の一方的な利益追及のためであり，快くないと考える隣国の王子様の側近は，お姫様を亡き者にするために道の途中に無数の刺客達を放った．

お姫様が通る道はすでに決められている．お姫様の通る道には合計 L 個の宿場がある．便宜上，出発地点および到着地点も宿場とし，各宿場を S1, S2, ... SL と呼ぶことにする．お姫様は最初に S1 におり，昇順に (S2, S3 ... という順番で) 宿場を訪れて，最終的に SL へ行くものとする．宿場では金銭を払って護衛を雇うことができ，お金がある限り好きな距離だけ契約してお姫様を守らせることができる．護衛を雇う費用は，距離1につき金1である．お姫様は通る区間内を部分的に守ってもらうことも出来ることに注意せよ．SiとSi+1間の距離はDi，SiとSi+1間で距離1につき刺客に襲われる回数の期待値はPiで与えられている．

お姫様が予算Mを持っていて，刺客に襲われる回数の期待値が最小になるように護衛を雇ったときの，目的地までに刺客に襲われる回数の期待値を求めよ．

Input

入力は複数のデータセットからなる．各データセットは以下のような形式をとる．

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) とその間を１単位距離移動したときに襲われる回数の期待値 Pi(0≦Pi<=10) からなる． 入力の終端は N=0, M=0 となるデータセットであらわされる．このデータセットに対しては計算結果を出力してはならない．

Output

各データセット毎に，お姫様が目的地までに刺客に襲われる回数の期待値を出力せよ．

Sample Input

2 8
5 6
4 5
3 1
5 10
5 10
5 10
0 0

Output for the Sample Input

5
140