B - 試験対策 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 233 点

問題文

高橋君は N 科目の試験を受けることになりました。各科目 i（1 \leq i \leq N）には、現在の実力で取れる得点 A_i があります。高橋君はすべての科目で合格点 T 以上の得点を取る必要があります。

高橋君は追加で勉強をすることで、各科目の得点を上げることができます。科目 i の得点を 1 点上げるには C_i 時間の勉強が必要です。すなわち、科目 i の得点を k 点上げるには k \times C_i 時間の勉強が必要です。なお、得点を下げることはできません。

現在の得点がすでに T 以上の科目については追加の勉強は不要であり、その科目にかかる勉強時間は 0 です。

高橋君がすべての科目の得点を T 以上にするために必要な合計勉強時間の最小値を求めてください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq T \leq 10^4
  • 0 \leq A_i \leq 10^4
  • 1 \leq C_i \leq 10^4
  • 入力はすべて整数である。

入力

N T
A_1 C_1
A_2 C_2
\vdots
A_N C_N
  • 1 行目には、科目数を表す整数 N と合格点を表す整数 T が、スペース区切りで与えられる。
  • 1 + i 行目（1 \leq i \leq N）には、i 番目の科目の現在の得点 A_i と、その科目の得点を 1 点上げるのに必要な勉強時間 C_i が、スペース区切りで与えられる。

出力

すべての科目の得点を合格点 T 以上にするために必要な合計勉強時間の最小値を 1 行で出力してください。

入力例 1

3 60
50 3
70 2
40 5

出力例 1

130

入力例 2

5 80
75 2
100 6
60 4
50 1
80 3

出力例 2

120

入力例 3

10 100
100 8
90 5
150 3
30 2
100 10
99 100
0 1
9999 4
50 3
85 7

出力例 3

645

Score : 233 pts

Problem Statement

Takahashi has to take exams in N subjects. For each subject i (1 \leq i \leq N), he can currently score A_i points with his present ability. Takahashi needs to score at least the passing mark T in every subject.

By studying additionally, Takahashi can raise his score in each subject. To raise the score in subject i by 1 point, C_i hours of study are required. That is, to raise the score in subject i by k points, k \times C_i hours of study are required. Note that he cannot lower his score.

For subjects where his current score is already T or higher, no additional study is needed, and the study time for that subject is 0.

Find the minimum total study time required for Takahashi to bring his score in every subject to T or higher.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq T \leq 10^4
  • 0 \leq A_i \leq 10^4
  • 1 \leq C_i \leq 10^4
  • All input values are integers.

Input

N T
A_1 C_1
A_2 C_2
\vdots
A_N C_N
  • The first line contains an integer N representing the number of subjects and an integer T representing the passing mark, separated by a space.
  • The (1 + i)-th line (1 \leq i \leq N) contains the current score A_i of the i-th subject and the study time C_i required to raise that subject's score by 1 point, separated by a space.

Output

Print in one line the minimum total study time required to bring the scores of all subjects to at least the passing mark T.

Sample Input 1

3 60
50 3
70 2
40 5

Sample Output 1

130

Sample Input 2

5 80
75 2
100 6
60 4
50 1
80 3

Sample Output 2

120

Sample Input 3

10 100
100 8
90 5
150 3
30 2
100 10
99 100
0 1
9999 4
50 3
85 7

Sample Output 3

645