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.
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).
For each case, print the maximal value on an single line.
Author: ZHANG, Rui