#3060. 「ROI 2016 Day1」围攻堡垒

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: Planet6174

题目描述

译自 ROI 2016 Day1 T1. Оборона крепости

墙有 n 段,第 i 段有 a_i 人进攻,在第 i 段上,一名防御者能击退 k_i 名攻击者。若某段有 x_i 人防守,进攻者不超过 x_i\times k_i 人,则此段不会被攻破;若进攻者超过 x_i\times k_i 人,则将有 a_i-x_i\times k_i 人攻破该段。 请将 s 名防御者分配到墙的各段上,使得攻破防守的攻击者尽可能少。

输入格式

第一行两个整数 n,s
接下来 n 行,每行两个整数,分别表示 a_i, k_i

输出格式

输出一行一个整数,表示在最优方案下攻破防守的攻击者数量。

样例

样例输入 1

1 10
8 1

样例输出 1

0

样例输入 2

3 3
4 2
1 1
10 8

样例输出 2

3

样例说明 2

第一段放两名防御者,第二段放一名防御者。

数据范围与提示

对于所有数据, 1 ⩽ n ⩽ 10^5, 1 ⩽ s ⩽ 10^9, 1 ⩽ a_i ⩽ 10^9, 1 ⩽ k_i ⩽ 10^9.

子任务 # 分值 1 ⩽ n ⩽ 1 ⩽ s ⩽ 1 ⩽ a_i ⩽ k_i 依赖子任务
1 17 100 10000 100 k_i = 1
2 21 1 ⩽ k_i ⩽ 2 1
3 23 1 ⩽ k_i ⩽ 100 1, 2
4 39 10^5 10^9   10^9   1 ⩽ k_i ⩽ 10^9 1 – 3