配点: 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) 卡片可以兑换奖品,所以不需要重写。