暂无测试数据。

DD 和萨摩耶一起去逛商店，店里一共有 $n$ 种商品，每种商品有两个属性 $a_i,b_i$，买 $x$ 个 $i$ 商品收获的喜悦值是 $x*max(a_i-xb_i,0)$，DD 现在最多可以买 $m$ 个商品（一种商品可以多次购买），请问获得的喜悦值最大是多少。

输入格式

第一行两个整数分别表示 $n,m$

接下来 $n$ 行，每行两个整数，分别表示 $a_i,b_i$

输出格式

输出喜悦值最大是多少

数据范围

对于 $20\%$ 的数据，$n \leq 20$

对于 $50\%$ 的数据，$n,m \leq 1000$

对于 $100\%$ 的数据，$n,m,a_i \leq 10^5,b_i \leq 10^3$

3 4
20 1
40 2
35 6

131