29020번 - ゲーム 다국어

문제

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 つのゼロからなる行で表される.

출력

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

제한

힌트

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

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