010 - ゲーム

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

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

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

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

N D A₁ B₁ ... A_N B_N

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

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

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

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

2 3
10 10
1 1
1 3
10 1
1 6
3 1
0 0

21
27
3

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

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