[ABC252Ex] K-th beautiful Necklace

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

[problemUrl]: https://atcoder.jp/contests/abc252/tasks/abc252_h $ 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 $

答えを出力せよ。

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 $ です。