围攻堡垒

题号：NC53328
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
Special Judge, 64bit IO Format: %lld

题目描述

译自 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行，每行两个整数，分别表示。

输出描述:

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

示例1

输入

复制

1 10
8 1

输出

复制

示例2

输入

复制

输出

复制

说明

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

备注:

对于所有数据，

CC-BY-SA，感谢LOJ分享，译文来自 https://loj.ac/problem/3060