← 返回题目列表

AtCoder · tenka1_2017_d

D. 整数

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

Seisu-ya,一家专门销售非负整数的商店,出售 N 非负整数。 i第一个整数是 A_i 并且拥有一个 工具 of B_i可能存在多个具有不同效用的相同整数。

高桥将在这家商店购买一些整数。他可以购买一组整数,其 按位或 小于或等于 K。他希望所购买整数的效用总和尽可能大。

求所购买整数的效用总和的最大可能值。

约束

  • 1 \leq N \leq 10^5
  • 0 \leq K < 2^{30}
  • 0 \leq A_i < 2^{30}(1\leq i\leq N)
  • 1 \leq B_i \leq 10^9(1\leq i\leq N)
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N K
A_1 B_1
:
A_N B_N

输出

打印所购整数的效用总和的最大可能值。


示例输入 1

3 5
3 3
4 4
2 5

示例输出 1

8

购买 2 和 3 为了实现最大可能的总效用, 8.


示例输入 2

3 6
3 3
4 4
2 5

示例输出 2

9

购买 2 和 4 为了实现最大可能的总效用, 9.


示例输入 3

7 14
10 5
7 4
11 4
9 8
3 6
6 2
8 9

示例输出 3

32