P6851 onu

小 C 和小 D 是好朋友。他们正在尝试一种全新的牌类游戏——onu！

为了增加一点趣味性，小 C 和小 D 每人买了 $v$ 颗糖用来当作筹码。 onu 的规则是这样的： 游戏共 $m$ 轮，由两人进行，一位先手，一位后手。在这里，我们默认先手的玩家是小 C，而后手的玩家是小 D。 在最开始时，小 C 会得到 $m$ 张牌，每张牌有其对应的花色、点数。而小 D 会得到 $n$ 张牌。 每一轮开始时，小 C 会打出一张牌，放在桌面上展示给小 D 看。 在此之后，小 D 需要跟牌，即打出他手上的一张牌，且该张牌必须满足其花色与小 C 打出的牌相同。若小 D 没有满足条件的牌或者是他**选择弃权（也就是说，可以选择当前回合是否打出牌）**，弃掉小 C 打出的牌后跳过该轮，视为小 D 败。 在小 D 打出满足要求的牌后，进行一次拼点，也即比较小 C 和小 D 打出的牌的点数：如果小 D 出的牌的点数**大于等于**小 C 的牌的点数，则小 D 胜，否则小 D 败。容易知道，这样不会出现平局的情况。 最后，胜的一方会从败的一方拿走 $c$ 颗糖，且双方均需弃掉打出的牌，并会**再从商店买等于自己打出的牌的点数颗糖**。例如小 C 和小 D 打的点数分别是 $3$ 和 $5$，那么小 C 会去购买 $3$ 颗糖，小 D 购买 $5$ 颗。 为了不破坏两人间的友好关系，不出现一方被另一方完全赢光的情况，他们在最开始买糖时，已经约定好了 $v \ge c \times m$。 现在，小 D 通过一些神秘手段，知道了小 C 在这 $m$ 轮中打出的所有牌，他希望在 $m$ 轮游戏进行之后，让自己的糖数尽量多。你可以帮他找到最优的方案吗？

无

无

#### 「样例 1 解释」 以 $(a, b)$ 来表示一张花色为 $a$，点数为 $b$ 的牌。 一开始，小 D 有 $4$ 颗糖。小 C 会依次打出 $(1, 6), (3, 5), (1, 4)$ 三张牌。 一种最优的方案是： 第一轮，小 C 打出第一张牌 $(1, 6)$，小 D 打出第二张牌 $(1, 2)$，小 D 负，被拿走 $1$ 颗糖，购买 $2$ 颗糖。此时其有 $5$ 颗糖。 第二轮，小 C 打出 $(3, 5)$，小 D 打出 $(3, 5)$，由于点数**大于等于**小 C 的牌，所以小 D 胜，拿到 $1$ 颗糖，购买 $5$ 颗糖。此时其有 $11$ 颗糖。 第三轮，小 C 打出 $(1, 4)$。由于小 D 在第一轮已经打出过第二张牌 $(1, 2)$ 了，所以没有牌能打，输出 $-1$ 并判小 D 负，被拿走 $1$ 颗糖，此时其有 $10$ 颗糖。 #### 「样例 2 解释」 最开始有 $5$ 颗糖。 第一轮时小 C 打出 $(1, 8)$，小 D 选择弃权，败，于是剩下了 $5 - 1 = 4$ 颗糖； 第二轮时小 C 打出 $(1, 4)$，小 D 打出 $(1, 5)$，胜，得到 $5 + 1$ 颗糖，故最终小 D 有 $10$ 颗糖。 ---- #### 「Special Judge 说明」 **请认真阅读输出格式**。 每个测试点仅有 $0$ 分和满分的区别。如果你的输出出现了以下情况，将会被判为 $0$ 分： - 输出格式不符，如没有正确换行，输出了一些奇奇怪怪的字符等。 - 输出的最优糖果数与标准答案不同。 - 打牌的方案不合法，即不能打出已经弃掉的牌，也不能打出花色与小 C 打出的牌不相同的牌。 - 按照你所输出的方案打完牌后，小 D 的剩余糖果数与你第一行所输出的数字不同。 --- #### 「数据范围」 **本题采用捆绑测试**。 - Subtask 1(10 points)：$n, m \le 5$； - Subtask 2(30 points)：$n, m \le 1000$； - Subtask 3(20 points)：$c = 0$； - Subtask 4(20 points)：$a _i = 1$； - Subtask 5(20 points)：无特殊限制。 所有数据保证 $1 \le n, m, a _i, b _i\le 10 ^5$，$0 \le c \le 10 ^5$，$c \times m \le v \le 10 ^{12}$。