A - Plant Growth Record Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は N 本の植物を育てています。

現在、i 番目の植物の高さは A_i ミリメートルです。それぞれの植物は1日あたり一定の長さだけ伸び、i 番目の植物は1日あたり B_i ミリメートル成長します。

現在から D 日後における、N 本の植物の高さの合計をミリメートル単位で求めてください。

なお、答えは 2 \times 10^{16} を超えない範囲に収まることが保証されます。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq D \leq 10^6
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq B_i \leq 10^5 (1 \leq i \leq N)
  • 入力はすべて整数である

入力

N D
A_1 B_1
A_2 B_2
\vdots
A_N B_N

1 行目には、植物の本数 N と経過日数 D がスペース区切りで与えられる。

i + 1 行目 (1 \leq i \leq N) には、i 番目の植物の現在の高さ A_i と1日あたりの成長量 B_i がスペース区切りで与えられる。

出力

現在から D 日後の N 本の植物の高さの合計値をミリメートル単位で 1 行に出力してください。

入力例 1

3 5
10 2
20 3
15 1

出力例 1

75

入力例 2

2 1
100 100
1 1

出力例 2

202

入力例 3

8 30
5 2
12 4
7 1
20 3
100 10
50 5
33 7
18 2

出力例 3

1265

入力例 4

20 365
1000 12
850 7
920 9
1100 15
760 6
1340 11
980 8
1230 10
670 5
890 7
1450 13
710 4
1600 14
540 3
1180 9
1300 12
1020 6
970 8
880 5
1500 16

出力例 4

86590

入力例 5

1 1000000
1000000000 100000

出力例 5

101000000000

Score : 200 pts

Problem Statement

Takahashi is growing N plants.

Currently, the height of the i-th plant is A_i millimeters. Each plant grows by a fixed length per day, and the i-th plant grows by B_i millimeters per day.

Find the total height of all N plants, in millimeters, after D days from now.

It is guaranteed that the answer does not exceed 2 \times 10^{16}.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq D \leq 10^6
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq B_i \leq 10^5 (1 \leq i \leq N)
  • All inputs are integers

Input

N D
A_1 B_1
A_2 B_2
\vdots
A_N B_N

The first line contains the number of plants N and the number of elapsed days D, separated by a space.

The (i + 1)-th line (1 \leq i \leq N) contains the current height A_i of the i-th plant and its daily growth amount B_i, separated by a space.

Output

Print on a single line the total height of all N plants after D days from now, in millimeters.

Sample Input 1

3 5
10 2
20 3
15 1

Sample Output 1

75

Sample Input 2

2 1
100 100
1 1

Sample Output 2

202

Sample Input 3

8 30
5 2
12 4
7 1
20 3
100 10
50 5
33 7
18 2

Sample Output 3

1265

Sample Input 4

20 365
1000 12
850 7
920 9
1100 15
760 6
1340 11
980 8
1230 10
670 5
890 7
1450 13
710 4
1600 14
540 3
1180 9
1300 12
1020 6
970 8
880 5
1500 16

Sample Output 4

86590

Sample Input 5

1 1000000
1000000000 100000

Sample Output 5

101000000000