配点 : $600$ 点

問題文

$N$ 個の宝石があります。$i$ 番目の宝石は色が $D_i$ で美しさが $V_i$ です。 ここで、色は $1,2,\ldots,C$ のいずれかであり、どの色の宝石も少なくとも $1$ 個存在します。

$N$ 個の宝石から、色が相異なる $C$ 個の宝石を選んでネックレスを作ります。（選ぶ順番は考えません。） ネックレスの美しさは選んだ宝石の美しさのビットごとの $\rm XOR$ となります。

全てのありえるネックレスの作り方のうち、美しさが $K$ 番目に大きいもののネックレスの美しさを求めてください。（同じ美しさの作り方が複数存在する場合、それらは全て数えます。）

制約

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

入力

入力は以下の形式で標準入力から与えられる。

$N$ $C$ $K$

$D_1$ $V_1$

$\vdots$

$D_N$ $V_N$

出力

答えを出力せよ。

4 2 3
2 4
2 6
1 2
1 3

5

以下のような $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$ となります。

3 1 2
1 0
1 0
1 0

0

$3$ 種類のネックレスを作ることができ、いずれも美しさは $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