CDR 的快乐购物 1658

Time Limit: 1 Sec Memory Limit: 256 MB

Submission：38 AC：11 Score：100

Description

CDR 最近很喜欢买东西，这天她来到一家商店，这家商店里有 $n$ 种她喜欢的商品，每种商品的数量都是无限的

但是众所周知，再喜欢的东西，买的太多了，就会没那么感兴趣了，CDR 当然也是如此

对 CDR 来说，每一样商品都有一个初始的开心值 $a_i$ 和重复购买值 $b_i$，也就是说每重复购买同一件商品，获得的开心值会下降 $b_i$

例如 CDR 总共购买了 $x$ 件第 $i$ 种商品，那么对她来说，每一件第 $i$ 种商品能够获得的开心值是 $a_i - x * b_i$

现在 CDR 准备最多购买 $m$ 件商品，她想知道，自己最多能获得多少开心值？

Input

输入第一行包含两个整数 $n, m$，含义如题
接下来 $n$ 行，每行包含两个整数 $a_i,b_i$，表示第 $i$ 种商品的信息

对于 $30\%$ 的数据：$1 \leq n, m \leq 10$
对于 $60\%$ 的数据：$1 \leq n, m \leq 20$
对于 $100\%$ 的数据：$1 \leq n,m \leq 1000, a_i \leq 10^5, b_i \leq 1000$

Output

输出一个整数，表示 CDR 最多能获得的开心值

Samples

input:

3 4 20 1 40 2 35 3

output:

134

Hint

CDR 可以购买 $3$ 件第 $2$ 种商品和 $1$ 件第 $3$ 种商品
共获得开心值为 $3 * (40 - 2 * 3) + 1 * (35 - 1 * 3) = 134$