Lead of Wisdom
TimeLimit:8000MS MemoryLimit:524288KB
64-bit integer IO format:%I64d
未提交 | 登录后收藏
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.
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$.
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$.
SampleInput
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
SampleOutput
297882000