题目描述

$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$ を二進表記した際の $2^k$ の位の数のうち一方のみが $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$

输出格式

答えを出力せよ。

题目大意

给定 $n$ 个珠子，每个珠子的颜色为 $d_i$，权值为 $v_i$。颜色共有 $c$ 种，且保证每种颜色至少有一颗珠子。你需要从 $n$ 个珠子种选择 $c$ 个颜色不同的珠子串成一条项链，其权值为其中所有珠子权值的异或和。你需要输出权值第 $k$ 大的项链的权值。只要选取的珠子不同，即使权值相同也算不同项链。数据保证可能构成的项链数不小于 $k$。

4 2 3
2 4
2 6
1 2
1 3

5

3 1 2
1 0
1 0
1 0

0

10 3 11
1 414213562373095048
1 732050807568877293
2 236067977499789696
2 449489742783178098
2 645751311064590590
2 828427124746190097
3 162277660168379331
3 316624790355399849
3 464101615137754587
3 605551275463989293

766842905529259824

提示

制約

• $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$ 種類のネックレスを作ることができる
• 入力に含まれる値は全て整数である

Sample Explanation 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$ となります。

Sample Explanation 2

$3$ 種類のネックレスを作ることができ、いずれも美しさは $0$ です。