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

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 


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

#include<iostream>
#define rint register int
using namespace std;
#define N 22
 
const int INF = 1e9 + 7;
int P[N], W[N];
int ans_e, ans_w, n, r;
 
void dfs(int k, int p, int e, int w, int d) {
    if (k == n) {
        if (d == r) {
            int me = min(p, e);
            if (ans_e < me) {
                ans_e = me;
                ans_w = w;
            } else if (ans_e == me) {
                ans_w = min(ans_w, w);
            }
        }
        return;
    }
    dfs(k + 1, p, e, w, d);
    if (P[k] > 0) dfs(k + 1, p + W[k] * P[k], e, w + W[k], d + 1);
    else dfs(k + 1, p, e - W[k] * P[k], w + W[k], d + 1);
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int T, tc = 1; cin >> T;
    while (T--) {
        cin >> n >> r;
        for (int i = 0; i < n; i++) cin >> W[i] >> P[i];
        ans_e = -INF, ans_w = INF;
        dfs(0, 0, 0, 0, 0);
        cout << ans_e << ' ' << ans_w << '\n';
    }
    return 0;
}