Train Ticket Allocation

A train starts at station 1, passes the stations in increasing order and stops at station $N$. A ticket from station $i$ to station $j$ can be sold whenever $i < j$.

The law fixes the price $C_{ij}$ of a ticket from station $i$ to station $j$ in advance, and the exact demand $D_{ij}$ for that pair is known before the trip, so you may sell anywhere from 0 to $D_{ij}$ tickets for it. The government also sets aside $O_{ij}$ free tickets from station $i$ to station $j$. A passenger holding one of those takes a seat but brings no income.

The train carries $P$ passengers at most. On every segment between two adjacent stations the number of passengers on board, counting the ones with government tickets, must not exceed $P$. Selling beyond the capacity is not allowed.

Find the largest income the trip can produce.

The first line contains the number of test cases $T$.

Each test case begins with a line holding the number of stations $N$ and the train capacity $P$. The next $N-1$ lines give the ticket prices. Line $i$ of that block holds $N-i$ numbers, and its $j$-th number is $C_{i,i+j}$, the price of a ticket from station $i$ to station $i+j$. The next $N-1$ lines give the demands $D_{ij}$ in the same format, and the $N-1$ lines after those give the number of free government tickets $O_{ij}$, again in the same format.

• $0 < T \le 100$
• $3 \le N \le 16$
• $0 < P \le 200$
• $0 < C_{ij} \le 1000$
• $0 \le D_{ij} \le 250$
• $0 \le O_{ij} \le 20$
• The government tickets alone never exceed the capacity.

For each test case, print the maximum possible income on its own line.