Train Tickets#1199
Tor Gunnar is a huge fan of trains. All his life, he would run around the house yelling "Toot Toot". So when he found out about a job opening at the local railway company, he immediately applied. Having studied hard, Tor Gunnar easily got the job. It was the happiest moment of his life! But to his great disappointment, he discovered that the contract said nothing about driving trains all day. He was instead assigned to the IT department, where he needed to develop a ticket management system. Specifically, he has to implement an algorithm for distributing tickets among all possible journeys on a train route.
Tor Gunnar lives in a strange country. Not only is its language barely understandable, but the government has also passed some unusual laws about ticket sales. For example, the price for traveling from station to station is fixed in advance. When processing ticket sales for a given trip, the exact demand for traveling between each pair of stations is also known. In addition, the government can reserve a certain number of tickets for its own use (these are, of course, free).
A train journey consists of several stations. You can travel from station to only if comes before in the list of stations. Each train has a certain capacity, and it is not allowed to carry more passengers between two adjacent stations than this capacity allows.
Tor Gunnar is puzzled and needs your help. Write a program to help him distribute the tickets in the best possible way.
The first line contains the number of test cases (0 < T \leq 100). Each test case begins with a line containing two integers, (3 \leq N \leq 16) and (0 < P \leq 200), the number of stations and the capacity of the train, respectively. Then follow N-1 lines describing the ticket prices, C_{ij} (0 < C_{ij} \leq 1000). The -th of these lines contains N-i numbers. The -th number of the -th line is the price of a ticket from station to station i+j. The next N-1 lines, in the same format, describe the ticket demand for each pair of stations, D_{ij} (0 \leq D_{ij} \leq 250). The next N-1 lines, also in the same format, describe the number of tickets reserved by the government, O_{ij} (0 \leq O_{ij} \leq 20).
The train journey starts at station and ends at station . Remember, the sum of passengers and tickets reserved for government use cannot exceed the train's capacity. Overloading the train is not allowed. The government will never reserve more tickets than the train's capacity.
For each test case, output on a separate line the maximum possible profit from the train trip.
Example 1