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

A. 小红的优惠券

  • 传统题
  • 1000ms
  • 256MiB

小红的优惠券

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

小红的优惠券

题目描述

小红的购物车结算金额为 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

来源

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

贪心专项特训

未参加
状态
已结束
规则
XCPC
题目
6
开始于
2026-10-11 18:00
结束于
2026-10-11 23:00
持续时间
5 小时
主持人
参赛人数
14