有一個 N*N 的矩陣 M，以及 N 個上面分別標記為 1, 2, ..., N 的石頭。現在你與朋友兩個人輪流取石頭，每次恰好取一個石頭。取完之後，如果你擁有數字 a 以及數字 b (兩個數字可以一樣)，那麼你可以獲得 M[a, b] 的分數。例如你拿到了標記為 1, 3, 5 的石頭，那麼你可以得到 M[1,1]+M[1,3]+M[1,5]+M[3,1]+M[3,3]+M[3,5]+M[5,1]+M[5,3]+M[5,5] 的分數。
問在兩位玩家都很聰明的情況下，你的分數至多可以贏過朋友幾分？
一個輸入檔包含多筆測試資料，第一行包含測資筆數 T (T<=100)。
對於每一筆測試資料，第一行有一個正整數 N 以及一個整數 P (P=1表示你是先手，P=0表示你是後手)，接下來有 N 行每行有 N 個非負整數表示矩陣 M。
至少佔 50% 分數的測試資料，N <= 20。
至少佔 90% 分數的測試資料，N <= 40。
對於所有的測試資料，N <= 100，矩陣的數字<=106。
對於每筆測試資料，請輸出先手分數減去後手分數的最大值。
1 3 0 2 8 1 3 5 5 3 2 7
-11
Migrated from old NTUJ.
ONTAK2010
| No. | Testdata Range | Score |
|---|