Minimum Cost to Train Top-notch Soldiers

In the Blue Bridge Kingdom, there are n soldiers who need to undergo special training to become top-notch warriors. For the i-th soldier, one individual training session costs p_i gold coins, and he must receive at least c_i training sessions to be considered a top-notch warrior.

To improve training efficiency, the kingdom offers a group training plan. In one group training session, every soldier receives one training session, and the total cost is S gold coins. The plan can be purchased any number of times (i.e. a soldier may participate in multiple group training sessions).

Your task as the training commander is to determine the minimum number of gold coins required so that every soldier is trained at least c_i times.

The total cost is computed as follows: if you purchase k group training sessions, every soldier obtains k training sessions, and for each soldier i you must additionally pay p_i \times max(0, c_i - k) coins to cover the deficit. The overall cost is:

\[ \text{Cost}(k) = k \times S + \sum_{i=1}^{n} p_i \times \max(0, c_i - k)\]

Your goal is to find the integer k (with 0 \le k \le max(c_i)) that minimizes the total cost.

inputFormat

The first line contains two integers n and S: the number of soldiers and the cost of a group training session, respectively.

Each of the following n lines contains two integers p_i and c_i, representing the cost per individual training for the i-th soldier and the minimum number of trainings required for that soldier.

outputFormat

Output a single integer: the minimum number of gold coins required so that every soldier becomes a top-notch warrior.

sample

3 10
1 2
2 1
3 3

13