AT_abc252_h [ABC252Ex] K-th beautiful Necklace

有 $N$ 个宝石。第 $i$ 个宝石的颜色为 $D_i$，美丽度为 $V_i$。 其中，颜色是 $1,2,\ldots,C$ 中的某一个，并且每种颜色的宝石至少有 $1$ 个。 从 $N$ 个宝石中，选择 $C$ 个颜色各不相同的宝石来制作项链。（选择的顺序不计入考虑。） 项链的美丽度为所选宝石美丽度的按位 $\rm XOR$。 请你求出所有可能制作项链的方法中，美丽度第 $K$ 大的项链的美丽度是多少。（如果有多种制作方法得到相同的美丽度，则这些方法都计数。） 按位 $\rm XOR$ 的定义如下： 对于整数 $A, B$，按位 $\rm XOR$，即 $A\ {\rm XOR}\ B$，定义为： - $A\ {\rm XOR}\ B$ 的二进制表示中，第 $2^k$ 位（$k\geq 0$）的数，如果 $A, B$ 的二进制表示中该位只有一个为 $1$，则为 $1$，否则为 $0$。 例如，$3\ {\rm XOR}\ 5 = 6$（二进制表示为：$011\ {\rm XOR}\ 101 = 110$）。

输入按以下格式从标准输入读入。 > $N$ $C$ $K$ > $D_1$ $V_1$ > $\vdots$ > $D_N$ $V_N$

请输出答案。

## 限制条件 - $1 \leq C \leq N \leq 70$ - $1 \leq D_i \leq C$ - $0 \leq V_i < 2^{60}$ - $1 \leq K \leq 10^{18}$ - 至少可以制作 $K$ 种项链 - 输入中的所有值均为整数 ## 样例解释 1 可以制作如下 $4$ 种项链： - 选择第 $1,3$ 个宝石。项链美丽度为 $4\ {\rm XOR}\ 2 = 6$。 - 选择第 $1,4$ 个宝石。项链美丽度为 $4\ {\rm XOR}\ 3 = 7$。 - 选择第 $2,3$ 个宝石。项链美丽度为 $6\ {\rm XOR}\ 2 = 4$。 - 选择第 $2,4$ 个宝石。项链美丽度为 $6\ {\rm XOR}\ 3 = 5$。 因此美丽度第 $3$ 大的项链美丽度为 $5$。 ## 样例解释 2 可以制作 $3$ 种项链，且它们的美丽度均为 $0$。 由 ChatGPT 4.1 翻译