7161: ABC252 —— Ex - K-th beautiful Necklace
[Creator : ]
Description
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 CC 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.)
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 CC 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.)
Input
Input is given from Standard Input in the following format:
$N\ C\ K$
$D_1\ V_1$
$\vdots$
$D_N\ V_N$
$N\ C\ K$
$D_1\ V_1$
$\vdots$
$D_N\ V_N$
Output
Print the answer.
Constraints
$1≤C≤N≤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.
$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.
Sample 1 Input
4 2 3
2 4
2 6
1 2
1 3
Sample 1 Output
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 2 Input
3 1 2
1 0
1 0
1 0
Sample 2 Output
0
There are three ways to make a necklace, all of which result in the beautifulness of 0.
Sample 3 Input
10 3 11
1 414213562373095048
1 732050807568877293
2 236067977499789696
2 449489742783178098
2 645751311064590590
2 828427124746190097
3 162277660168379331
3 316624790355399849
3 464101615137754587
3 605551275463989293
Sample 3 Output
766842905529259824