문제1578--Max K Trace

### 1578: Max K Trace

실행시간 제한: 10 Sec  메모리사용 제한: 128 MB
제출: 131  통과: 49
[제출] [채점기록] [묻고답하기]

#### 문제 설명

The digit in element i chracter j of mat will correspond to the value in row i column j of an N x N matrix.
Choosing k rows and k columns determines a k x k submatrix of mat.
To compute the trace of such a submatrix S, first extract S from mat and reindex the rows and columns maintaining the original order. Add together all values along the main diagonal of the reindexed matrix (values with the same reindexed row and column).
Find the largest trace considering all possible k x k submatrices.

#### 입력 설명

The first line of the input gives a number of test cases, T. Each test case consists of an integer n and n by n digits.
The first line of each test cases contains two positive integer N(1<=N<=50), the size of the mat and K(1<=K<=N), size of submatrix.
The following N lines contain exactly N character per line and describe elements of mat. j-th Character in i-th row of mat denotes a element, mati,j.

#### 출력 설명

For each test case, write a answer in single line.

#### 입력 예시 Copy

4
3 3
123
456
789
2 1
12
93
5 3
12689
55555
55555
55555
55555
15 5
494599520389852
303896953907791
287493604901139
149554299340006
893640109028429
564962730433253
075854577852319
453201529585621
950489162577436
630040569640126
415141646262027
837673828874883
785041862021729
850806584119109
217671590991247

#### 출력 예시 Copy

15
9
16
45