跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#NCT11255782. 小红的优惠券

小红的优惠券

小红的优惠券

题目描述

小红的购物车结算金额为 nn 元,她手中有 mm 张优惠券。第 jj 张优惠券的规则为“满 aja_j 元立减 bjb_j 元”:若 n≥ajn\geq a_j,使用该券后需支付 n−bjn-b_j 元。

小红至多使用一张优惠券,也可以不使用。请问她最少需要支付多少元?

输入格式

第一行输入两个整数 n,mn,m,其中 1≤n≤1051\leq n\leq 10^5,1≤m≤1001\leq m\leq100。

接下来 mm 行,每行输入两个整数 aj,bja_j,b_j,其中 1≤bj≤aj≤1051\leq b_j\leq a_j\leq10^5。

输出格式

输出一个整数,表示最少需要支付的金额。

样例 1

100 3
300 50
200 30
50 5
95

来源

原题。题意按原题整理,测试数据由本站独立构造。