← 返回题目列表

Codeforces · 241/B

B. 朋友

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

你有 n 个朋友,你想给他们拍 m 张照片。每张图片中应恰好出现您的两个朋友,并且任何两张图片都不应包含同一对朋友。因此,如果您有 n = 3 个朋友,您可以拍摄 3 张不同的照片,每张照片包含一对您的朋友。

您的每个朋友都有一个吸引力级别,该吸引力级别由第 i 个朋友的整数 ai 指定。你知道,包含第 i 个和第 j 个朋友的图片的吸引力等于整数 ai 和 aj 的异或(异或运算)。

您希望以最大化照片吸引力总和的方式拍摄照片。你必须计算这个值。由于结果可能无法容纳 32 位整数,因此将其打印为模 1000000007 (109 + 7)。

输入

输入的第一行包含两个整数 n 和 m $$( 1 \leq n \leq 5 \cdot 1 0 ^ { 4 } ; \; 0 \leq m \leq \frac { n \cdot ( n - 1 ) } { 2 } )$$ — 好友数量和要拍摄的照片数量。

下一行包含 n 个空格分隔的整数 a1, a2, ..., an (0 ≤ ai ≤ 109) — 朋友的吸引力值。

输出

唯一的输出行应包含一个整数 - 图片吸引力的最佳总和。

示例

输入 #1

3 1
1 2 3

输出 #1

3

输入 #2

3 2
1 2 3

输出 #2

5

输入 #3

3 3
1 2 3

输出 #3

6