이어달리기

한 팀은 정해진 순서로 N명의 선수를 이어 달리게 한다. 대회는 D일 동안 진행되며, 매일 한 명의 선수만 달린다.

선수 교체는 하루가 시작될 때에만 할 수 있다. 한 번 다음 선수로 넘어가면 이전 선수는 다시 달릴 수 없다. 모든 선수는 정해진 순서대로 정확히 한 번 참가해야 하며, 각 선수는 연속으로 최소 1일, 최대 3일을 달려야 한다.

각 선수에게는 세 개의 기록 (a, b, c)가 주어진다. 이 값은 그 선수가 각각 1일, 2일, 3일 연속으로 달렸을 때 갈 수 있는 거리이다. 모든 올바른 기록은 a <= b <= c를 만족해야 한다.

N명의 선수 순서는 이미 정해져 있다. 각 선수가 며칠씩 달릴지를 정해, 정확히 D일 동안 갈 수 있는 총거리의 최댓값을 구하라.

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스는 다음과 같이 주어진다.

• 첫 줄에 선수 수 N이 주어진다. (1 <= N <= 50)
• 다음 줄에 대회 기간 D가 주어진다. (1 <= D <= 150)
• 이어지는 N개의 줄에는 선수가 출전하는 순서대로 각 선수의 기록 a b c가 주어진다.

각 기록은 1일, 2일, 3일 연속으로 달렸을 때의 거리이다.

각 테스트 케이스마다 한 줄에 하나의 정수를 출력한다.

정확히 D일 동안 달릴 수 있는 총거리의 최댓값을 출력한다. 기록이 올바르지 않거나 규칙을 만족하도록 선수를 배정할 수 없다면 -1을 출력한다.