Giải bài trực tuyến

FSoft company has just employed N programmers. The leader wants them to be separated into M groups satisfying: each group's quantity is equal and each person is belong to only one group. After interviewing them and analyzing their CV(s), the leader has summarized the table A where A_ij values the effect whether progammer i and j are in the same group.
The leader needs your help to find out the most effective separation. A separation's effect is the sum of all group's effect; each group's effect is the sum of all pair of person in that group.

Input

- The first line contains N, M.
- Next N line(s), each line contains N number describing the table A. (A_ii=0; A_ji=A_ij)

Output

- The first line contains the effect of your separation.
- Next M lines contains the list of each group following your separation.

Example

Input:
4 2
0 1 2 3
1 0 5 1
2 5 0 2
3 1 2 0

Output:
8
1 4
2 3

Limitations

- 1 ≤ N ≤ 100.
- 1 ≤ M ≤ 10. (N mod M = 0)

Scoring

- There are 10 test cases; in each test case, let your separation's effect be RES, let the answer be ANS; if your written programmer list is logical, you will get the score = (RES/ANS)⁴x10.
- The overall score is the sum of the scores you got in each test case.