Equipment

A research institute has developed $N$ kinds of equipment for soldiers to wear. Each piece is rated in five categories: attack, defense, sight, portability, and ease of use. Every score is an integer between $0$ and $10000$ inclusive, so a piece of equipment is described by five integers.

A soldier wears exactly $K$ pieces of equipment. When several pieces are worn, each category improves independently by the maximum score in that category among the worn pieces. For example, if two pieces have sight scores $10$ and $15$, then wearing both improves sight by the maximum, $15$. This maximum is called the extended score of that category.

You want to choose exactly $K$ of the $N$ pieces so that the sum of the extended scores over the five categories is as large as possible. Find that maximum.

Let the scores of piece $i$ be $(r_{i,1}, r_{i,2}, r_{i,3}, r_{i,4}, r_{i,5})$ with $0 \le r_{i,j} \le 10000$. If $S$ is the set of worn pieces, the goal is to maximize $\sum_{j=1}^{5} \max_{i \in S} r_{i,j}$ subject to $|S| = K$.

For example, let $N = 4$, $K = 2$, with the following scores.

• Piece 1: $(30, 30, 30, 30, 0)$
• Piece 2: $(50, 0, 0, 0, 0)$
• Piece 3: $(0, 50, 0, 50, 10)$
• Piece 4: $(0, 0, 50, 0, 20)$

Wearing pieces 1 and 3 gives an extended-score sum of $30 + 50 + 30 + 50 + 10 = 170$, which is the largest achievable value.

The first line contains the number of test cases $T$. For each test case, the first line contains two integers $N$ and $K$ ($1 \le N \le 10000$, $1 \le K \le N$). Each of the following $N$ lines contains the scores of one piece of equipment as five space-separated integers $r_{i,1}$, $r_{i,2}$, $r_{i,3}$, $r_{i,4}$, $r_{i,5}$, each between $0$ and $10000$ inclusive.

For each test case, print on its own line the maximum possible sum of extended scores when wearing $K$ of the $N$ pieces of equipment.