← 返回题目列表

AtCoder · awc0004_b

B. 电池电量

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

分数: 233 分

问题陈述

高桥正在开发一种系统来监控充电状态 N 智能手机。

时间 0,每部智能手机的电池电量 i (1 \leq i \leq N)是 A_i 毫安时。每部智能手机 i 以恒定速率消耗电池 B_i mAh/s 从时间 0 开始。但是,电池电量不会低于 0 毫安时。

即智能手机的电池电量 i 时间 t (t \geq 0)是 \max(A_i - B_i \times t,\ 0) 毫安时。

查找所有设备的总电池电量 N 当时的智能手机 T.

约束

  • 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
  • 第一行包含一个整数 N 代表智能手机的数量和一个整数 T 表示计算总电池电量的时间,以空格分隔。
  • 线 2 通过 N+1 提供每部智能手机的信息。
  • 线 1 + i 包含一个整数 A_i 代表智能手机的初始电池电量 i 和一个整数 B_i 表示每秒的电池消耗量,以空格分隔。

输出

输出当时所有智能手机的总电池电量 T 作为单行上的整数。


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