J-溪染的优惠券_牛客小白月赛35

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

溪染在 ${2}$ 月 ${30}$ 日参加了某宝的福利活动

她得到了 ${n}$ 张优惠券

每张优惠券可以对任意商品生效

每张优惠券有 ${2}$ 个参数， ${a}$ 和 ${b}$

代表满 ${a}$ 元可以减免 ${b}$ 元（保证 ${a}$ 大于等于 ${b}$ ）

溪染在 ${2}$ 月 ${31}$ 日想买一个商品，商品需要 ${k}$ 元

可惜溪染是个穷鬼，只能依靠优惠券过活

于是她去查看了优惠券使用方法，如下：

优惠券只能一张一张按顺序使用，且每张优惠券只能使用一次

对于一个商品，和一张优惠券编号为 ${i}$ ，如果商品价格为 ${k}$ 元且大于等于 $a_i$ 元，那么使用优惠券后商品价格可以减少 $b_i$ 元，此时商品价格更新为 $(k-b_i)$ 元

如果需要使用下一张优惠券编号为 ${j}$ ，那么必须满足 $a_j \leq (k-b_i)$ ,此时商品价格更新为 $(k-b_i-b_j)$ 元,以此类推

溪染想要知道她最少支付多少软妹子才能买到商品

于是她找到了你，希望你帮她计算一下

第一行输入两个正整数，表示优惠券的张数和商品价格。
接下来输入n行，每行两个非负整数，含义见上文。

仅一行表示问题的答案，最少需要支付多少钱。

示例1

复制

复制

优惠券使用顺序为：
使用2号优惠券，商品更新为96元
使用4号优惠券，商品更新为48元
使用1号优惠券，商品更新为24元