ゲーム

N 種類のゲームがある．これから D 日間，ゲームを一日に一つずつ遊ぶ．あるゲームを複数回遊んでもよく，また一回も遊ばないゲームがあってもよい．

i 番目のゲームの楽しさの初期値は Ai である．このゲームを一日遊ぶと，翌日には，その楽しさは Bi だけ減少する．逆に，このゲームを一日遊ばないでいると，翌日には，その楽しさは（初期値を超えない範囲で） Bi だけ回復する．すなわち，ある日の i 番目のゲームの楽しさが x であった場合，このゲームの翌日の楽しさは，このゲームを遊んだ場合は x - Bi に，遊ばなかった場合は min(x + Bi, Ai) に，それぞれ変化する．

D 日間でのゲームの遊び方として考えられるものは ND 通りあるが，このうち遊んだゲームの楽しさの合計が最大となるような遊び方をしたときの，その楽しさの合計の値を求めよ．

入力は 50 個以下のデータセットからなる．各データセットは次の形式で表される．

N D

A1 B1

...

AN BN

1 行目には整数 N および D が与えられる．N はゲームの種類数であり，1 ≤ N ≤ 100,000 を満たす．D はゲームを遊ぶ日数であり，1 ≤ D ≤ 100,000 を満たす．

続く N 行には，N 種類のゲームの情報が与えられる．このうち i 番目の行には整数 Ai および Bi が与えられる．Ai は i 番目のゲームの楽しさの初期値であり， 1 ≤ Ai ≤ 100,000 を満たす．Bi は i 番目のゲームを遊んだときの楽しさの減少量であり， 1 ≤ Bi ≤ 100,000 を満たす．

入力の終わりは 2 つのゼロからなる行で表される．

各データセットに対し，答えを一行に出力せよ．

最初のデータセットでは，ゲーム 1，ゲーム 2，ゲーム 1 の順番で遊んだとき，楽しさの合計が 10 + 1 + 10 = 21 となる．

二番目のデータセットでは，ゲーム 1 を三日連続で遊んだとき，楽しさの合計が 10 + 9 + 8 = 27 となる．