djb 的快乐购物

题目描述

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

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

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

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

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

输入格式

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

输出格式

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

数据范围

对于 $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 3

样例输出

134

样例解释

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