Lead of Wisdom

Problem Description

In an online game, "Lead of Wisdom" is a place where the lucky player can randomly get powerful items. There are $k$ types of items, a player can wear at most one item for each type. For the $i$-th item, it has four attributes $a_i,b_i,c_i$ and $d_i$. Assume the set of items that the player wearing is $S$, the damage rate of the player $DMG$ can be calculated by the formula: [DMG=\left(100+\sum_{i\in S} a_i\right)\left(100+\sum_{i\in S} b_i\right)\left(100+\sum_{i\in S} c_i\right)\left(100+\sum_{i\in S} d_i\right)] Little Q has got $n$ items from "Lead of Wisdom", please write a program to help him select which items to wear such that the value of $DMG$ is maximized.

Input

The first line of the input contains a single integer $T$ ($1 \leq T \leq 10$), the number of test cases. For each case, the first line of the input contains two integers $n$ and $k$ ($1 \leq n,k \leq 50$), denoting the number of items and the number of item types. Each of the following $n$ lines contains five integers $t_i,a_i,b_i,c_i$ and $d_i$ ($1\leq t_i\leq k$, $0\leq a_i,b_i,c_i,d_i\leq 100$), denoting an item of type $t_i$ whose attributes are $a_i,b_i,c_i$ and $d_i$.

Output

For each test case, output a single line containing an integer, the maximum value of $DMG$.

Sample Input

1
6 4
1 17 25 10 0
2 0 0 25 14
4 17 0 21 0
1 5 22 0 10
2 0 16 20 0
4 37 0 0 0

Sample Output

297882000

Source

2020 Multi-University Training Contest 2