시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 193 62 43 30.935%

문제

국방 과학 연구소 (Korea Defense and Science Institute, KDSI) 에서는 최근 몇 년간 군인 개인이 착용할 새로운 장비를 꾸준히 개발하고 있고, 얼마 전에 N 종류의 장비를 출시했다.

KDSI는 새로 만든 모든 장비의 성능을 평가했고, 5가지 범주로 나눠서 평가를 해 점수로 나타냈다. 다섯 가지 범주는 공격 향상, 방어 향상, 시력 향상, 휴대성, 사용 편이성이다. 모든 점수는 0보다 크거나 같고, 10,000보다 작거나 같은 정수이다. 따라서, 모든 장비는 정수 다섯개로 나타낼 수 있따.

KDSI에서는 군인들의 능력의 평균과 비용 문제 때문에, 군인 한 명이 착용할 수 있는 장비의 개수를 K개로 제한했다. 만약, 한 군인이 장비를 하나만 착용한 경우에, 그 장비의 점수만큼 능력이 향상된다. 두 개 이상 착용한 경우에는 각 범주마다 독립적으로 능력이 향상되며, 착용한 장치의 점수의 최대값만큼 능력이 향상된다. 에를 들어, 장비 a와 b의 시력 향상 점수가 10과 15일때, 두 장비를 착용하면 최대값인 15만큼 시력이 향상된다. 이 때, 최대 점수 15를 범주의 확장 점수라고 한다. 따라서, 이 예에서 {a, b}의 시력 향상 확장 점수는 15가 된다.

KDSI는 군인 한 명이 장비를 K개 착용했을 때, 가장 능력 향상이 많이 되는 조합을 찾으려고 한다. 특수 목적 군인의 경우에는 특정 범주의 점수가 훨씬 더 중요하다. 하지만, 범용성을 위해 각 범주의 확장 점수의 합이 최대가되는 조합을 찾으려고 한다. N개의 장비 중에서 확장 점수의 합이 최대가 되는 장비 K개 조합을 찾는 프로그램을 작성하시오.

장비가 N개를 {1, ..., N}로, 각 장비의 점수 Ri를 다섯 정수 Ri = (ri,1, ri,2, ri,3, ri,4, ri,5) (모든 i=1,...,N과 j=1,...,5에 대해서 0 ≤ ri,j ≤ 10,000)로 나타낼 수 있다. 이 때, K (1 ≤ K ≤ N)가 주어졌을 때, 확장 점수의 합이 가장 큰 장비 K개를 찾아야 한다.

예를 들어, N=4, K=2이고, Ri가 다음과 같은 경우가 있다.

R1 = (30, 30, 30, 30, 0)
R2 = (50, 0, 0, 0, 0)
R3 = (0, 50, 0, 50, 10)
R4 = (0, 0, 50, 0, 20)

R1과 R3을 착용하면 향상 점수는 30+50+30+50+10 = 170이 되고, 이 점수가 가능한 값 중 가장 큰 값이다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 N과 K가 주어진다. (1 ≤ N ≤ 10,000, 1 ≤ K ≤ N) 다음 N개 줄에는 0보다 크거나 같고, 10,000보다 작거나 같은 정수 다섯개가 주어지며, 이 정수는 각 장비의 점수 ri,1, ri,2, ri,3, ri,4, ri,5를 나타낸다. 인접한 두 정수 사이에는 빈 칸이 하나 있다.

출력

각 테스트 케이스 마다, 장비 N개중 K개를 착용했을 때, 가장 큰 향상 점수의 합을 출력한다.

예제 입력

2
4 2
30 30 30 30 0
50 0 0 0 0
0 50 0 50 10
0 0 50 0 20
5 1
10 20 60 0 0
0 0 20 50 30
30 50 20 20 0
10 10 10 20 30
30 0 20 10 20

예제 출력

170
120

힌트

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Daejeon 2011 D번