溪染在2{2}2月30{30}30日参加了某宝的福利活动 她得到了n{n}n张优惠券 每张优惠券可以对任意商品生效 每张优惠券有2{2}2个参数，a{a}a和b{b}b 代表满a{a}a元可以减免b{b}b元（保证a{a}a大于等于b{b}b） 溪染在2{2}2月31{31}31日想买一个商品，商品需要k{k}k元
溪染在2{2}2月30{30}30日参加了某宝的福利活动 她得到了n{n}n张优惠券 每张优惠券可以对任意商品生效 每张优惠券有2{2}2个参数，a{a}a和b{b}b 代表满a{a}a元可以减免b{b}b元（保证a{a}a大于等于b{b}b） 溪染在2{2}2月31{31}31日想买一个商品，商品需要k{k}k元 可惜溪染是个穷鬼，只能依靠优惠券过活 于是她去查看了优惠券使用方法，如下： 优惠券只能一张一张按顺序使用，且每张优惠券只能使用一次 对于一个商品，和一张优惠券编号为i{i}i，如果商品价格为k{k}k元且大于等于aia_iai元，那么使用优惠券后商品价格可以减少bib_ibi元，此时商品价格更新为(k−bi)(k-b_i)(k−bi)元 如果需要使用下一张优惠券编号为j{j}j，那么必须满足aj≤(k−bi)a_j leq (k-b_i)aj≤(k−bi),此时商品价格更新为(k−bi−bj)(k-b_i-b_j)(k−bi−bj)元,以此类推 溪染想要知道她最少支付多少软妹子才能买到商品 于是她找到了你，希望你帮她计算一下
（图片来源网络，侵删）
