G. catch

catch 是一款游戏，游戏有两个轨道，有一些方块会从轨道上方落下，玩家可以在轨道下方接住这些物块，并获得这个物块的分数。

假设有 $n$ 个物块依次下落，你一开始在第一个轨道处，最多可以切换 $k$ 次位置。(注：在第一个方块下落时，你就可以选择切换轨道)。

请求出你的最高得分。

第一行两个整数 $n,k$ ，表示物块的数量和切换轨道的最多次数。

然后 $n$ 行，每行两个整数 $a_i,b_i$，其中$a_i$ 表示轨道编号，$b_i$ 表示物块的价值。

输出一行一个整数表示最大的得分。

样例输入

7 2
2 3
1 4
1 5
2 3
2 4
1 5
1 3

样例输出

24

$n\leq 20000,k\leq 2000,a_i\in \{1,2\},1 \leq b_i\leq 10000$。