#P7783. Lead of Wisdom

Lead of Wisdom

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 kk types of items, a player can wear at most one item for each type. For the ii-th item, it has four attributes ai,bi,cia_i,b_i,c_i and did_i. Assume the set of items that the player wearing is SS, the damage rate of the player DMGDMG 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 nn items from "Lead of Wisdom", please write a program to help him select which items to wear such that the value of DMGDMG is maximized.

Input

The first line of the input contains a single integer TT (1≤T≤101 \leq T \leq 10), the number of test cases. For each case, the first line of the input contains two integers nn and kk (1≤n,k≤501 \leq n,k \leq 50), denoting the number of items and the number of item types. Each of the following nn lines contains five integers ti,ai,bi,cit_i,a_i,b_i,c_i and did_i (1≤ti≤k1\leq t_i\leq k, 0≤ai,bi,ci,di≤1000\leq a_i,b_i,c_i,d_i\leq 100), denoting an item of type tit_i whose attributes are ai,bi,cia_i,b_i,c_i and did_i.

Output

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

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