Ex - K-th beautiful Necklace 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 600 点

問題文

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

Score : 600 points

Problem Statement

We have N gemstones. The color and beauty of the i-th gemstone are D_i and V_i, respectively.
Here, the color of each gemstone is one of 1, 2, \ldots, C, and there is at least one gemstone of each color.

Out of the N gemstones, we will choose C with distinct colors and use them to make a necklace. (The order does not matter.) The beautifulness of the necklace will be the bitwise \rm XOR of the chosen gemstones.

Among all possible ways to make a necklace, find the beautifulness of the necklace made in the way with the K-th greatest beautifulness. (If there are multiple ways with the same beautifulness, we count all of them.)

What is bitwise \rm XOR?

The bitwise \rm XOR of integers A and B, A \oplus B, is defined as follows:

  • When A \oplus B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if either A or B, but not both, has 1 in the 2^k's place, and 0 otherwise.
For example, 3 \oplus 5 = 6. (In base two: 011 \oplus 101 = 110.)

Constraints

  • 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}
  • There are at least K ways to make a necklace.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N C K
D_1 V_1
\vdots
D_N V_N

Output

Print the answer.

Sample Input 1

4 2 3
2 4
2 6
1 2
1 3

Sample Output 1

5

There are four ways to make a necklace, as follows.

  • Choose the 1-st and 3-rd gemstones to make a necklace with the beautifulness of 4\ {\rm XOR}\ 2 =6.
  • Choose the 1-st and 4-th gemstones to make a necklace with the beautifulness of 4\ {\rm XOR}\ 3 =7.
  • Choose the 2-nd and 3-rd gemstones to make a necklace with the beautifulness of 6\ {\rm XOR}\ 2 =4.
  • Choose the 2-nd and 4-th gemstones to make a necklace with the beautifulness of 6\ {\rm XOR}\ 3 =5.

Thus, the necklace with the 3-rd greatest beautifulness has the beautifulness of 5.

Sample Input 2

3 1 2
1 0
1 0
1 0

Sample Output 2

0

There are three ways to make a necklace, all of which result in the beautifulness of 0.

Sample Input 3

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

Sample Output 3

766842905529259824