시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 0 0 0 0.000%

문제

이어달리기 경기가 서울에서 열린다. 경기 규칙은 다음과 같다.

  1. 각 팀은 정확히 N 명의 선수로 이루어진다.
  2. D 일 동안 가장 긴 거리를 달린 팀이 우승한다.
  3. 날마다 각 팀에서 한 명씩 달린다.
  4. 주자 교체는 하루가 시작될 때에만 가능하다.
  5. 각 팀에 소속된 선수는 최소 1일, 최대 3일을 달려야 한다.
  6. 한 번 교체된 선수는 다시 참가할 수 없다.

'칙칙폭폭' 팀이 이어달리기에 참가하기로 했다. '칙칙폭폭' 팀의 감독은 N 명의 선수가 D일 동안 경기에 나설 순서는 정했지만, 누가 정확히 며칠씩 달릴지는 아직 정하지 못했다. 감독은 각 선수의 기록을 보고서 누가 며칠씩 달릴지를 결정하고자 한다. 각 선수의 기록은 세 숫자로 이루어진다. i(i=1,2,3) 번째 숫자는 각 주자가 i 일 연속해서 달릴 때 갈 수 있는 거리를 나타낸다. (단위는 킬로미터.) 예를 들어 어느 선수의 기록이 (4,7,9)라면, 이 선수는 하루 달리면 4 킬로미터, 이틀 달리면 7 킬로미터, 사흘 달리면 9 킬로미터를 갈 수 있다. 모든 기록 (a,b,c)는 부등식 a ≤ b ≤ c을 만족한다.

감독은 '칙칙폭폭' 팀이 D일 동안 갈 수 있는 최장 거리를 알고 싶다. 예를 들어, N=3, D=4이고 세 선수의 기록이 (4,7,8), (2,4,6), (4,5,6)이라고 하자. 그렇다면 이 팀이 4일 동안 갈 수 있는 최장 거리는 13킬로미터이다. 첫 선수가 이틀 동안 (1,2 일차) 7 킬로미터, 둘째 선수가 하루 동안 (3 일차) 2 킬로미터, 셋째 선수가 하루동안 (4 일차) 4 킬로미터를 가면 된다.

'칙칙폭폭' 팀이 D 일 동안 갈 수 있는 최장거리를 알려주는 프로그램을 작성하라.

입력

입력은 T 개의 테스트 케이스로 구성된다. 입력 첫 줄에 테스트 케이스의 개수 T가 입력된다. 각 테스트 케이스는 N+2줄로 구성된다. 테스트 케이스의 첫 줄에는 '칙칙폭폭' 팀의 선수의 숫자를 나타내는 정수 N (1≤ N ≤ 50)이 주어진다. (단위는 명) 둘째 줄에는 이어달리기 대회가 진행되는 기간을 나타내는 정수 D (1≤ D ≤150)이 주어진다. (단위는 일) 이어서 N 줄 동안 각 선수의 기록이 주어진다. 선수의 기록이 주어지는 순서는 선수가 경기에 출전하는 순서이다.

출력

각 테스트 케이스마다 한 줄씩 출력한다. 각 줄에는 D 일 동안 달릴 수 있는 거리를 나타내는 정수 하나가 출력되어야 한다. 기록에 오류가 있거나, 대회 규칙에 따라 선수를 편성하는 것이 불가능 할 경우에는 -1을 출력한다.

예제 입력

2
3
4
4 7 8
2 4 6
4 5 6
2
7
2 3 5
3 6 8

예제 출력

13
-1

힌트