← 返回题目列表

AtCoder · awc0016_b

B. 考试准备

中文机器翻译题面 查看原题

分数: 233 分

问题陈述

高桥必须参加考试 N 科目。对于每个科目 i (1 \leq i \leq N),他目前可以得分 A_i 以他现在的能力来分。高桥需要至少获得及格分数 T 每个科目。

通过额外学习,高桥可以提高每门科目的分数。为了提高科目分数 i by 1 点, C_i 需要学习时数。也就是提高科目分数 i by 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
  • 第一行包含一个整数 N 代表受试者数量和一个整数 T 代表及格分数,以空格分隔。
  • 的 树的 (1 + i)- 第行 (1 \leq i \leq N) 包含当前分数 A_i 的 i第科目及学习时间 C_i 需要将该科目的分数提高 1 点,以空格分隔。

输出

在一行中打印出使所有科目的分数至少达到及格分数所需的最短总学习时间 T.


示例输入 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