题目描述

在蓝桥王国中，有 ~n~ 名士兵，这些士兵需要接受一系列特殊的训练，以提升他们的战斗技能。对于第 ~i~ 名士兵来说，进行一次训练所需的成本为 ~p_i~ 枚金币，而要想成为顶尖战士，他至少需要进行 ~c_i~ 次训练。
为了确保训练的高效性，王国推出了一种组团训练的方案。该方案包含每位士兵所需的一次训练，且总共只需支付 ~S~ 枚金币（组团训练方案可以多次购买，即士兵可以进行多次组团训练）。
作为训练指挥官，请你计算出最少需要花费多少金币，才能使得所有的士兵都成为顶尖战士？

输入格式

输入的第一行包含两个整数 ~n~ 和 ~S ~，用一个空格分隔，表示士兵的数量和进行一次组团训练所需的金币数。
接下来的 ~n~ 行，每行包含两个整数 ~p_i~ 和 ~c_i~，用一个空格分隔，表示第 ~i~ 名士兵进行一次训练的金币成本和要成为顶尖战士所需的训练次数。

输出格式

输出一行包含一个整数，表示使所有士兵成为顶尖战士所需的最少金币数。

输入输出样例 #1

输入 #1

3 6
5 2
2 4
3 2

输出 #1

16

说明/提示

花费金币最少的训练方式为：进行 ~2~ 次组团训练，花费 ~2 \times 6 = 12~ 枚金币，此时士兵 ~1, 3~ 已成为顶尖战士；再花费 ~4~ 枚金币，让士兵 ~2~ 进行两次训练，成为顶尖战士。总花费为 ~12 + 4 = 16~。

对于 ~40\%~ 的评测用例，~1 \le n \le 10^3~，~1 \le p_i, c_i \le 10^5~，~1 \le S \le 10^7~。

对于所有评测用例，~1 \le n \le 10^5~，~1 \le p_i, c_i \le 10^6~，~1 \le S \le 10^{10}~。