← 返回题目列表

AtCoder · joi2017yo_b

B. 点卡

中文机器翻译题面 查看原题

配点: 100 点

問題

JOI商店街提供积分卡服务。每张点卡都有 有 2N 方格。当您购买产品时,您可以抽奖,根据结果,正方形上会出现“中奖”或“未中奖”的标记。同一个正方形上也会有一个标记 不会被按 2 次。 超出2N 个方格 N 写有1个以上方格的获胜符号的点卡可以兑换奖品。另外,点卡上的标记是1 每平方 1 您可以将其重写为日元。

打趣你 2N 所有方格都填满的点卡 我有 M 。点卡 i (1 \leqq i \leqq M)有A_i 获胜分数和B_i 异常值被标记。和你打交道 我想要的不仅仅是 M - 1 奖品。

JOI Kimiga 求获得 M - 1 或更多奖品所需的最低成本。 在


入力

输入是 有一条 M + 1 行组成。

1 行中,2 整数 N, M (1 \leqq N \leqq 1\,000,1 \leqq M \leqq 1\,000)以空格作为分隔符。这是针对点卡的。 有 2N 方格,还有JOI君 表示您拥有 M 点卡。

继续 M 行 i 行目 (1 \leqq i \leqq M) 分别是 点卡上写有 2 整数 A_i, B_i (0 \leqq A_i \leqq 2N,0 \leqq B_i \leqq 2N,A_i + B_i = 2N)。 i 有 A_i 获胜分数和 指示 B_i 异常值已被标记。

出力

JOI Kimiga 求获得 M - 1 获得至少所需的最低成本 输出为 1 行。 在


入力例 1

4 5
1 7
6 2
3 5
4 4
0 8

出力例 1

4

入力例 1 中,点卡 1 标记结束 3 将您的积分卡更换为特殊标记。 3 标记结束 1 如果你要求他们将其更改为命中标记,4 日元 4 \: (= 5 - 1) 卡片可以兑换奖品,这是最低成本。 在


入力例 2

5 4
5 5
8 2
3 7
8 2

出力例 2

0

入力例 2 中,我们已经 3 \: (= 4 - 1) 卡片可以兑换奖品,所以不需要重写。