你有 n 个一次函数

你现在要构造出 n 个整数，使得

• $x_i >= 0$

• $\sum{x_i}$ <= M$

给定 M ，最大化 $\sum{f(x_i)}$

输入格式

第一行两个正整数 n,k 。

随后 行每行两个整数ki,bi 。

输出格式

一个整数表示最大的答案。

样例输入

3 4

2 3

2 2

-2 -1

样例输出

12