P12117 [NWRRC2024] Misère

Préférence 是一种在东欧非常流行的纸牌游戏。通常使用一副 32 张的牌组，包含四种花色（黑桃、梅花、方块、红心）中 7 到 10 的数字牌以及 J、Q、K、A。每轮游戏中，三位玩家各发 10 张牌，剩下 2 张作为底牌。随后进入叫牌阶段，玩家需要承诺赢得至少一定数量的墩。其中一种特殊的叫牌是 misère，即承诺无论其他玩家如何出牌都不赢得任何墩。 本题考虑一种变体游戏，使用修改后的牌组包含 $A \cdot B$ 张牌，其中 $A$ 表示花色数量，$B$ 表示每个花色的牌面等级数。例如标准 32 张牌组中 $A=4$，$B=8$。为方便起见，花色编号为 $1$ 到 $A$，牌面等级编号为 $1$ 到 $B$。 我们需要解决关于这个变体游戏的谜题。在这个变体中，当满足以下条件时，我们称 misère 是 *保证* 的：对于每个花色，将你手中该花色的牌按等级排序为 $b_1 < b_2 < \cdots < b_k$（$k$ 为该花色牌的数量），必须满足对所有 $1 \le i \le k$ 有 $b_i \le 2i - 1$。若手中没有该花色的牌（$k=0$），则自动满足条件。 你手中有 $n$ 张牌，允许选择任意 $x$ 张不拥有的牌加入手牌，然后从 $n+x$ 张牌中丢弃 $x$ 张，最终保留 $n$ 张牌。你的任务是找到最小的 $x$，使得可以通过上述操作将手牌转变为保证的 misère。

每个测试包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 1000$）。接下来是各测试用例描述。 每个测试用例第一行包含三个整数 $n$、$A$ 和 $B$，分别表示手牌数量、花色数量和牌面等级数量（$1 \le n \le 5000$；$1 \le A, B \le 10^9$）。 随后 $n$ 行每行包含两个整数 $a_i$ 和 $b_i$，描述一张牌的花色和等级（$1 \le a_i \le A$；$1 \le b_i \le B$）。所有手牌都是唯一的。 保证所有测试用例的 $n$ 之和不超过 $5000$。

对于每个测试用例，输出最小的非负整数 $x$，使得可以通过先添加 $x$ 张新牌再丢弃 $x$ 张牌的操作，将手牌转变为保证的 misère。 可以证明这样的 $x$ 总是存在。