장비

한 연구소에서 군인이 착용할 장비 $N$종을 개발했다. 각 장비는 다섯 가지 범주, 즉 공격, 방어, 시력, 휴대성, 사용 편이성에 대해 평가되며, 각 범주의 점수는 $0$ 이상 $10000$ 이하의 정수이다. 따라서 장비 하나는 다섯 개의 정수로 나타낼 수 있다.

군인 한 명은 장비를 정확히 $K$개 착용한다. 여러 장비를 착용하면 각 범주마다 독립적으로, 착용한 장비들의 그 범주 점수 중 최댓값만큼 능력이 향상된다. 예를 들어 두 장비의 시력 점수가 각각 $10$과 $15$이면, 둘 다 착용했을 때 시력은 최댓값인 $15$만큼 향상된다. 이 최댓값을 그 범주의 확장 점수라고 한다.

$N$개의 장비 중 정확히 $K$개를 골라 착용할 때, 다섯 범주의 확장 점수의 합이 최대가 되도록 하고 싶다. 그 최댓값을 구하시오.

장비 $i$의 점수를 $(r_{i,1}, r_{i,2}, r_{i,3}, r_{i,4}, r_{i,5})$로 나타내자 ($0 \le r_{i,j} \le 10000$). 착용할 장비들의 집합을 $S$라 하면, 목표는 $|S| = K$이면서 $\sum_{j=1}^{5} \max_{i \in S} r_{i,j}$를 최대로 만드는 것이다.

예를 들어 $N = 4$, $K = 2$이고 각 장비의 점수가 다음과 같다고 하자.

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

장비 1과 장비 3을 함께 착용하면 확장 점수의 합은 $30 + 50 + 30 + 50 + 10 = 170$이고, 이것이 가능한 최댓값이다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 두 정수 $N$과 $K$가 주어진다 ($1 \le N \le 10000$, $1 \le K \le N$). 이어지는 $N$개의 줄에는 각 장비의 점수가 공백으로 구분된 다섯 개의 정수 $r_{i,1}$, $r_{i,2}$, $r_{i,3}$, $r_{i,4}$, $r_{i,5}$로 주어지며, 각 값은 $0$ 이상 $10000$ 이하의 정수이다.

각 테스트 케이스마다, $N$개의 장비 중 $K$개를 착용했을 때 얻을 수 있는 확장 점수 합의 최댓값을 한 줄에 하나씩 출력한다.