問題文

$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$)。

制約

• $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$

出力

答えを出力せよ。

入力例 1

4 2 3
2 4
2 6
1 2
1 3

出力例 1

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

入力例 2

3 1 2
1 0
1 0
1 0

出力例 2

0

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

入力例 3

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

出力例 3

766842905529259824