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
a_{i} and
b_{i}, where
a_{i} is the amount of pleasure you get when you tell your opinion about this opponent;
b_{i} 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 ≤
K ≤
min(
N, 20)). Next
N lines contain two integer numbers each —
ith opponent parameters
a_{i} and
b_{i} (0 ≤
a_{i} ≤ 50; 0 ≤
b_{i} ≤ 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
