该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定 $n$ 个数字，第 $i$ 个数字的大小为 $a_i$ ，且它属于第 $b_i$ 个集合里。在一个集合中选择一个数字，得到的价值是这个数字的大小，选择多个数字，得到的价值是这些数字的异或和。

你得到的总价值是所有集合的价值之和。你至多从中选择 $m(m \leq n)$个数字，使得这些数字的总价值最大。

输入描述

第一行输入两个正整数 $n, m(1 \leq n, m \leq 2000)$

接下来 $n$ 行，每行给出两个正整数 $a_i, b_i(1 \leq a_i, b_i \leq 2000)$ ，分别表示第 $i$个数字的大小和所属集合的编号。

输出描述

输出一行一个整数表示答案

3 3
7 1
6 1
3 1

7

【样例 1 说明】

由于三个数字都在第一个集合，如果选择 6 和 7，则获得的价值为7 异或 6 = 1。只选一个数字 7 是最优的方案。

3 3
7 1
6 3
3 1

13

【样例 2 说明】

对于 1 号集合，只选一个数字 7 是最优的方案，对于 3 号集合，选择一个 6。得到的总价值为 6+7=13

5 3
6 1
5 1
2 1
3 3
2 3

10

【数据范围】