366. Computer Game

Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



BerSoft company recently released new computer game, where you play against N opponents. During the game you need to tell to K opponents your opinion about them. You feel pleasure after that and get several score points after that. Each opponent described by two parameters ai and bi, where ai is the amount of pleasure you get when you tell your opinion about this opponent; bi amount of score points you get in that case. Let us denote A and B summary pleasure and score points that you get during the game. You have never played this game; therefore you don't know what is now what is more advantageous: get more pleasure or score points. You decided to make these values as close as possible. Your task is to select K opponents in a way that minimizes |A - B|. If there are several ways to do it, choose one that maximizes A + B.

Input
The first line of the input file contains integer number N, K (1 ≤ N ≤ 60000; 1 ≤ Kmin(N, 20)). Next N lines contain two integer numbers each — i-th opponent parameters ai and bi (0 ≤ ai ≤ 50; 0 ≤ bi ≤ 50).

Output
On the first line of the output file print values A and B. Print numbers of K selected opponents on the second line. Print numbers in ascending order. If there are several solutions, output any of them.

Example(s)
sample input
sample output
4 2 
1 2 
2 3 
4 1 
6 2
6 4 
2 3

sample input
sample output
5 3 
13 11 
3 17 
15 20 
6 13 
17 9
36 33 
1 4 5

sample input
sample output
3 1 
1 1 
3 3 
2 2
3 3 
2




Online Contester Team © 2002 - 2010. All rights reserved.