题目描述

一群兔崽子发动叛乱，意图干掉阿兔。然而，阿兔非常聪明，他能够以最佳的攻击顺序逐一制服兔崽子们。

战斗过程如下

1. 所有未被制服的兔崽子同时对阿兔发动攻击，造成总伤害为它们攻击力之和。
2. 阿兔选择一个最佳的目标进行攻击。若目标的血量被降低至 $0$ ，则该兔崽子被制服，不再参与后续攻击。
3. 当所有兔崽子都被制服时，叛乱结束。

已知共有 $n$ 只兔崽子，每只兔崽子的初始血量为 $h_{i}$ 和攻击力为 $a_{i}$（下标从 $1$ 开始），若阿兔的攻击力为 $k$。 你的任务是计算阿兔最少会受到多少总伤害，并将结果对 $10^{9}+7$ 取模。

输入格式

第一行包含两个个正整数 $n,k \ (1\leq n \leq 2*10^{5},1\leq k \leq 10^{9})$，分别表示兔崽子的数量和阿兔的攻击力。

接下来的 $n$ 行，每行包含两个正整数 $h_{i},a_{i} \ (1\leq h_{i},a_{i} \leq 10^{9})$，分别表示编号为 $i$ 的兔崽子的初始血量和攻击力。

输出格式

输出一个整数，表示阿兔在最佳攻击顺序下最少会受到的总伤害值，结果对 $10^{9}+7$ 取模。

2 11
21 1
10 1000

1003

解释 #1

第一轮：

所有兔崽子的总攻击力为 $1001$。 阿兔选择攻击 编号 $2$ 的兔崽子，并成功将其制服（只需 $1$ 轮攻击）。

阿兔受到的总伤害为 $1001$。

第二轮：

剩余兔崽子的总攻击力为 $1$（仅编号 $1$ 的兔崽子未被制服）。

阿兔选择攻击 编号 $1$ 的兔崽子，消耗一次攻击，该兔崽子剩余生命值为 $10$。

阿兔受到的额外伤害为 $1$。

第三轮：

剩余兔崽子的总攻击力仍为 $1$。

阿兔再次攻击 编号 $1$ 的兔崽子，成功将其制服（最后一击）。

阿兔受到的额外伤害为 $1$。

结束：

所有兔崽子被制服，叛乱结束。

此进攻顺序下，阿兔受到的伤害为 $1003$ 点，是最小的，可以证明这是最佳方案。