小藍最近正在玩一款 RPG 游戲。他的角色一共有 N 個可以加攻擊力的技能。其中第 i 個技能首次升級可以提升 A_i 點攻擊力，以后每次升級增加的點數(shù)都會減少 B_i。(上取整) 次之后，再升級該技能將不會改變攻擊力。 

現(xiàn)在小藍可以總計升級 M 次技能，他可以任意選擇升級的技能和次數(shù)。請你計算小藍最多可以提高多少點攻擊力？ 

輸入第一行包含兩個整數(shù) N 和 M。

以下 N 行每行包含兩個整數(shù) A_i 和 B_i。

3 6
10 5
9 2
8 1

47

對于 40% 的評測用例，1 ≤ N, M ≤ 1000；

對于 60% 的評測用例，1 ≤ N ≤ 10⁴ , 1 ≤ M ≤ 10⁷；

對于所有評測用例，1 ≤ N ≤ 10⁵，1 ≤ M ≤ 2 × 10⁹，1 ≤ A_i , B_i ≤ 10⁶。