Untitled

It is science class of middle standard of MissMihye.

Today they are studying acid and alkalireactions. There are N bottles of acid/alkaline/neutral acid.

On each glass bottle its weight is markedin gram unit, the reactivity is indicated in -3 to +3, + means acidic solution,- means alkaline solution and 0 means neutral And absolute value of these show strengthof reactivity.

Here 1 g of +2 strength acid can react with1g of -2 alkaline and it will generate 2 calories of energy and resultingsolution would be neutral. So when we mix acid and alkaline it would generateenergy as much as solution is neutralized. Like 10g of +3 acid have acidstrength 10x3 = +30 and it can neutralize alkaline of 15g and -2 (strength -30)to generate energy 30 calories and weight of resultant material is 10+ 15 g =25g.

 

Miss Mihye is asked to select R chemicalssuch that it generate maximum energy. She should select exact R bottles, notless than R bottles.

 

Let’s take an example :

Glass Bottle	1	2	3	4	5
Weight	30	10	70	50	50
Reactivity	1	-1	0	-3	-1

 

Here we need to select 3 bottles.

For {1, 2, 5} .. Weight is 90 and energy is30( 30x1 = +30, it can neutralize only 30 strength of alkaline even we havealkaline -10 -50 = -60. )

 

For {1,3,4} weight is 150, energy is again30.

In case we have same energy for somecombination we select with less weight.

[Input]

First line have number of test cases: T

Next line have N (5<= N <= 20):number of glass bottles and R(2<=R<=20) number of bottles Miss Mihye shouldselect.

Next we have weight Wi Wi(1<= Wi <= 100),Pi(-3 <= Pi <= 3) reactivity for N bottles.

[Output]

Output maximum calories which can begenerated along with weight..

 

[Inputexample

5 // Testcase 5

5 3

30 1 10 -1 70 0 50 -3 50 -1

5 3

30 -3 30 3 40 1 30 -3 10 -2

5 2

30 -1 90 2 70 -3 40 0 60 2

5 3

60 0 50 -1 20 2 80 3 40 2

5 5

80 -2 20 0 80 1 60 3 50 -2

[Outputexample]

30 90

90 70

180 160

50 110

260 290

Input:
15
5 3
23 1 41 -1 17 0 95 -3 45 -1 
5 3
43 -3 43 3 64 1 13 -3 81 -2 
5 5
73 0 99 2 67 1 34 0 76 2 
7 5
46 0 35 -1 42 2 28 3 54 2 36 3 20 -2 
7 7
18 1 86 3 95 -2 20 -3 36 -2 33 1 64 -3 
7 6
77 -3 65 -2 58 2 36 -3 97 -2 100 0 26 -1 
10 2
17 2 15 -1 21 -2 99 -3 88 -2 42 3 11 2 16 1 65 -3 55 -1 
10 2
1 -1 20 2 44 2 40 1 8 -2 50 -1 38 -1 10 -1 38 0 13 -3 
10 3
28 -3 31 -2 5 2 22 -2 17 1 99 1 82 -1 60 3 35 2 96 -1 
15 9
25 2 96 2 84 -1 63 -3 42 -1 95 0 34 -3 59 1 30 3 7 3 46 0 50 -3 66 2 52 2 24 0 
15 13
56 -2 62 0 95 -3 82 3 81 0 85 0 98 0 21 3 75 0 83 3 10 1 10 -3 54 -3 41 -1 75 -3 
15 6
25 -3 71 2 90 0 37 -1 99 -3 14 -3 76 -1 27 -1 10 1 85 3 12 1 54 1 75 0 54 -1 70 -3 
20 18
29 -3 57 -1 7 3 98 -2 49 3 10 0 40 2 86 -1 87 -3 56 3 41 -1 81 -3 50 -3 80 -1 6 -1 14 -3 55 3 78 -1 53 1 35 1 
20 17
82 3 36 3 4 2 48 3 85 1 71 3 88 0 67 3 47 2 40 3 32 1 34 1 28 -3 54 -3 89 -1 100 3 66 -3 31 2 51 3 54 0 
20 6
35 1 22 0 38 0 17 3 64 -2 43 2 6 1 65 3 1 -1 63 -3 32 -2 35 0 58 -3 59 -3 94 2 1 -2 47 0 46 0 58 2 34 -3 

Output:
23 81
162 188
0 349
75 161
309 352
116 359
126 107
50 94
180 184
525 482
568 735
463 391
669 827
533 834
499 397