B - Battery Level Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 233 点

問題文

高橋君は、N 台のスマートフォンの充電状況を監視するシステムを開発しています。

時刻 0 において、各スマートフォン i（1 \leq i \leq N）のバッテリー残量は A_i mAh です。各スマートフォン i は、時刻 0 以降、B_i mAh/s の一定の速度でバッテリーを消費します。ただし、バッテリー残量は 0 mAh 未満にはなりません。

すなわち、時刻 t（t \geq 0）におけるスマートフォン i のバッテリー残量は \max(A_i - B_i \times t,\ 0) mAh です。

時刻 T における N 台すべてのスマートフォンのバッテリー残量の合計を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq T \leq 10^9
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_i \leq 10^9
  • 入力はすべて整数

入力

N T
A_1 B_1
A_2 B_2
\vdots
A_N B_N
  • 1 行目には、スマートフォンの台数を表す整数 N と、バッテリー残量の合計を求めたい時刻を表す整数 T が、スペース区切りで与えられる。
  • 2 行目から N+1 行目では、各スマートフォンの情報が与えられる。
  • 1 + i 行目には、スマートフォン i の初期バッテリー残量を表す整数 A_i と、毎秒のバッテリー消費量を表す整数 B_i が、スペース区切りで与えられる。

出力

時刻 T における全てのスマートフォンのバッテリー残量の合計を整数として 1 行で出力せよ。

入力例 1

3 5
100 10
30 8
50 20

出力例 1

50

入力例 2

4 10
200 15
80 10
150 30
60 5

出力例 2

60

入力例 3

5 1000000000
1000000000 1
500000000 2
100 1000000000
999999999 1
1 1

出力例 3

0

Score : 233 pts

Problem Statement

Takahashi is developing a system to monitor the charging status of N smartphones.

At time 0, the battery level of each smartphone i (1 \leq i \leq N) is A_i mAh. Each smartphone i consumes battery at a constant rate of B_i mAh/s from time 0 onwards. However, the battery level does not go below 0 mAh.

That is, the battery level of smartphone i at time t (t \geq 0) is \max(A_i - B_i \times t,\ 0) mAh.

Find the total battery level of all N smartphones at time T.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq T \leq 10^9
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_i \leq 10^9
  • All inputs are integers

Input

N T
A_1 B_1
A_2 B_2
\vdots
A_N B_N
  • The first line contains an integer N representing the number of smartphones and an integer T representing the time at which to calculate the total battery level, separated by a space.
  • Lines 2 through N+1 give the information for each smartphone.
  • Line 1 + i contains an integer A_i representing the initial battery level of smartphone i and an integer B_i representing the battery consumption per second, separated by a space.

Output

Output the total battery level of all smartphones at time T as an integer on a single line.

Sample Input 1

3 5
100 10
30 8
50 20

Sample Output 1

50

Sample Input 2

4 10
200 15
80 10
150 30
60 5

Sample Output 2

60

Sample Input 3

5 1000000000
1000000000 1
500000000 2
100 1000000000
999999999 1
1 1

Sample Output 3

0