
62  ZOJ Monthly, January 2008  1008
Xiao Ming is a fan of comic. After watching the comic "Fate Stay Night", he wants to make an MV for it. As a crazy fan, he has collected enough materials for the MV. Xiao Ming considers the quality of the MV is not which materials used but how used. So he also make a table v about the score about pairs of materials. (vij is the score which gotten when material j be put next to material i, vij may not be equal to vji.) To simpify the program, all materials are only 1 time unit. You task is to write a program to tell Xiao Ming the maximal value which we can getfor a L time units MV. Input There are multiple test cases. First line is the number of test cases. For each case, the first line is two integer n(0 < n <= 100) and L(1 <= L <= 1000000), n is the number of materials, L is the length of the MV. There will be n * n integers in next n lines, they are v(vij < 32768). Output For each case, print the maximal value on an single line. Sample Input
1 Sample Output
10 Author: ZHANG, Rui 