Relay Race

A team has N runners who must run in a fixed order. The race lasts for D days, and exactly one runner runs each day.

A runner can be changed only at the start of a day. Once the team moves on to the next runner, a previous runner cannot run again. Every runner must participate exactly once in the given order, and each runner must run for at least 1 day and at most 3 consecutive days.

Each runner has a record (a, b, c). These values are the distances the runner can cover when running for 1, 2, and 3 consecutive days, respectively. A valid record must satisfy a <= b <= c.

The order of the N runners is already fixed. Decide how many days each runner runs so that the team runs for exactly D days and the total distance is as large as possible.

The first line contains the number of test cases T.

Each test case is given as follows.

• The first line contains the number of runners N. (1 <= N <= 50)
• The next line contains the race duration D. (1 <= D <= 150)
• The next N lines contain one runner record a b c per line, in the order in which the runners must participate.

Each record gives the distance for running 1, 2, and 3 consecutive days.

For each test case, print one integer on its own line.

Print the maximum total distance the team can cover in exactly D days. If any record is invalid or it is impossible to assign runners according to the rules, print -1.