题目描述

BerSoft 公司发布了一款新的电脑游戏。游戏中共有 $N$ 个对手，你必须从中选择恰好 $K$ 个，并向他们表达你的看法。

对于第 $i$ 个对手：

• 选择他会获得 $a_i$ 点愉悦值；
• 同时获得 $b_i$ 点游戏分数。

设所选 $K$ 个对手的愉悦值总和为 $A$，分数总和为 $B$。

因为你还不知道愉悦值和游戏分数哪一个更重要，所以希望二者尽可能接近。你的任务是选择恰好 $K$ 个对手，使：

1. $|A-B|$ 最小；
2. 如果有多种方案达到相同的最小 $|A-B|$，则在这些方案中使 $A+B$ 最大。

输入格式

第一行包含两个整数 $N,K$：

• $1\le N\le60000$；
• $1\le K\le\min(N,20)$。

接下来 $N$ 行，第 $i$ 行包含两个整数 $a_i,b_i$：

$0\le a_i,b_i\le50$。

输出格式

第一行输出两个整数 $A,B$，表示所选方案的愉悦值总和与游戏分数总和。

第二行输出 $K$ 个整数，表示选中的对手编号。编号必须按严格递增顺序输出。

如果存在多种最优方案，可以输出任意一种。

样例 1

4 2
1 2
2 3
4 1
6 2

6 4
2 3

样例 2

5 3
13 11
3 17
15 20
6 13
17 9

36 33
1 4 5

样例 3

3 1
1 1
3 3
2 2

3 3
2

判题说明

本题可能存在多组不同的最优选择，因此需要特殊判题程序验证选中的下标以及对应的 $A,B$ 是否达到全局最优目标。