Driven by recent fierce competition in retail market, The Store, one of the largest department store chains in Thailand starts a project to boost customer visiting. Since The Store has good relation with “Joy Boy”, a talented superstar, The Store decided that having “Joy Boy” perform concert once per month is the best way to lure more customer to the store. The project last c months, hence, there will be c Joy Boy concerts to be performed. The Store has s department stores in different cities, one store per one city. Each city is numbered from 1 to s. The Store has to decide which store should have the concert on each month. The planning department of The Store has calculated, for every pair stores and months, the expected profit if Joy Boy performs a concert on a particular store in a particular month. Being nice and all, Joy Boy does not charge for his performance but he ask The Store to pay for his traveling and hotel expense. The planning department also knows the traveling cost for every pair of stores. Of course, it is possible to have Joy Boy stay at the same store for the next month and it might be some expense even though he performs at the same store. Be noted that Joy Boy does not charge the cost traveling to the first concert. The Store asks you to project the maximum possible profits minus traveling cost from Joy Boy’s Thailand tour for The Store. Input The first line in the input contain a single number, n, the number of test cases, 0 < n ≤ 10. Then, n test cases follow. For each test case, it contains (2 ∗ s + 1) lines using following format. • The first line contains 2 numbers, s and c where s is the number of stores and c is the number of concerts. 0<s≤100,0<c≤50. • The next s lines contain the projected profits. Each line for each store, starting from store 1 to store s. Each line contains c numbers — the projected profits for each month if Joy Boy would play at this store, starting from the first month to the c-th month. The profit is nonnegative integer not exceeding 1,000. • Finally, the last s lines contain the costs of moving from one store to other store. Each line for the cost of going from each store, starting from store 1 to store s. Each line contains s number — the cost of moving from the current store to each store, starting from store 1 to store s. The cost is non-negative integer not exceeding 100. Output For each test case, output one line with the maximum possible profit minus traveling cost. Sample Input 3 34 1 3 20 40 50 20 1 2 20 50 50 1 0 10 10 10 0 10 10 10 0
2/2 33 20 20 20 20 20 20 20 20 20 0 20 40 20 0 40 40 10 0 24 10 20 10 20 20 10 20 10 05 50 Sample Output 170 60 65