There are N jewels of different mass, power and value, numbered from 1 to N. Jewel i has mass M[i], power P[i] and value V[i]. A magician wishes to string together some of these jewels to form a necklace and imbue it with magical powers. However, the jewels are very different in quality, and the magician has to ensure that the necklace follows some strict quality regulations before it can be imbued with magic.
The quality difference between two jewels, D(i,j), can be calculated from their masses and powers, as follows:
D(i,j) = M[i]*M[j]*(P[i]-P[j]) + P[i]*P[j]*(M[i]-M[j])
Suppose the necklace consists of K ≥ 3 jewels J[0], J[1], ..., J[K-1] aligned in a ring. Then for every consecutive triplet (a,b,c) = (J[i],J[(i+1) mod K],J[(i+2) mod K]) [0 ≤ i < K], if the following triangle inequality holds,
D(a,b) + D(b,c) ≥ D(a,c),
we call the triplet a triangular triplet.
The magic works best when the necklace has the least number of triangular triplets. Thus, the magician wishes to use a subset of the N jewels to construct a necklace with at least 3 jewels that minimises the number of triangular triplets. If there are multiple such necklaces, the magician wishes to find one whose jewels' total value is maximum. Of course, he needs your help!
Input
The first line contains a single integer
T (1 ≤
T ≤ 50), the number of test cases. The
T test cases are then given consecutively. For each test case:
- The first line contains a single integer N (3 ≤ N ≤ 120).
- The ith of the next N lines contains three integers M[i], P[i] and V[i]. (1 ≤ M[i], P[i], V[i] ≤ 1,000).
Output
For each test case, output 2 space-separated integers on a single line: the minimum number of triangular triplets on a necklace and the maximum total value of jewels on such a necklace.
Sample Input
2
3
1 2 3
4 5 6
7 8 9
3
1 2 3
4 5 6
7 8 9
Sample Output
0 18
0 18
Explanation
The D(i,j) values are as follows:
| i\j | 1 | 2 | 3 |
|---|
| 1 | 0 | -42 | -138 |
|---|
| 2 | 42 | 0 | -204 |
|---|
| 3 | 138 | 204 | 0 |
|---|
J[0] = 2, J[1] = 3, J[2] = 1 is a viable necklace, as no consecutive triplet on the necklace is triangular:
- D(2,3) + D(3,1) = -204 + 138 = -66 < D(2,1) = 42
- D(3,1) + D(1,2) = 138 + (-42) = 96 < D(3,2) = 204
- D(1,2) + D(2,3) = -42 + (-204) = -246 < D(1,3) = -138
The total value of the jewels is 3+6+9 = 18.