Welcome to ZOJ
 Contests Information Problems Runs Statistics Ranklist Clarification
62 - ZOJ Monthly, January 2008 - 1008
MV Maker

Time Limit: 5 Seconds      Memory Limit: 32768 KB

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
3 3
-9 5 6
-6 -9 4
-4 4 -8

Sample Output

10

Author: ZHANG, Rui

Submit    Status