COETEST5

Chú A là một người phân phối nông sản nhỏ ở thành phố D.

Hiện tại, chú A có một số khách hàng ở một số tỉnh thành, chú sẽ vận chuyển hàng bằng cách gửi hàng theo những xe đi tới những tỉnh thành đó. Những xe vận chuyển sẽ cần có một lượng hàng nhất định mới có thể gửi đi, nên mỗi lần gửi hàng, chú A chỉ đủ hàng để gửi cho 3 xe hàng. Để thu được lợi nhuận lớn nhất, chú A cần giảm thiểu chi phí vận chuyển đến các khách hàng.

Tuy nhiên, do những xe vận chuyển hàng này chỉ đi trên những tuyến đường cố định của họ nên với mỗi tuyến xe thì lợi nhuận mà chú A thu được là khác nhau.

[Example]

Giả sử chú A đã tính toán được lợi nhuận sau khi giao hàng tới 7 khách hàng và chú A đang biết 5 tuyến xe di chuyển qua những điểm giao hàng này, lợi nhuận của từng xe khi giao tới 7 khách hàng được cho trong bảng kích thước 5x7 dưới đây.

 * Hàng đầu tiên thể hiện lợi nhuận của tuyến xe thứ nhất đến lần lượt 7 khách hàng, tương tự với tuyến xe thứ 2 đến tuyến xe thứ 5.

Để có tổng lợi nhuận lớn nhất, chú A cần chọn 3 tuyến xe lần lượt là 1, 2 và 3 để gửi hàng, khi đó các tuyến xe được chọn để gửi hàng cho các khách hàng sẽ như bảng dưới đây.

Tuyến xe số 1 sẽ phụ trách cho khách hàng số 7; tuyến xe ở vị trí số 2 sẽ phụ trách cho khách hàng số 1, 2 và 4; tuyến xe ở vị trí số 3 sẽ phụ trách cho khách hàng 3, 5 và 6.

Tổng lợi nhuận sẽ là: 99 + 82 + 93 + 99 + 80 + 91 + 97 = 641.

Cho thông tin về lợi nhuận của từng tuyến xe sau khi giao hàng tới từng khách hàng, hãy giúp chú A tìm ra 3 tuyến xe để gửi hàng sao cho tổng lợi nhuận thu được là lớn nhất, in ra giá trị lợi nhuận lớn nhất này.

[Input]

Dòng đầu tiên là số lượng test case T (T<=50). Thông tin về mỗi test case như sau:

Dòng đầu tiên là 2 số N (3<=N<10) và M (5<=M<= 1000) tương ứng là số lượng tuyến xe mà chú A biết và số lượng khách hàng cần giao hàng của chú A.

Trong N dòng tiếp theo, mỗi dòng thứ i gồm M số nguyên dương D (1<=D<= 100), tương ứng là lợi nhuận mà chú A đã tính được của tuyến xe thứ i sau khi giao hàng đến M khách hàng.

[Output]

Đưa ra output trên T dòng tương ứng với T test case.

Mỗi test case in ra"#tc", với tc là số thứ tự của test case, đánh số bắt đầu từ 1, tiếp theo là một dấu cách và kết quả tương ứng của test case đó.

Kết quả in ra là tổng lợi nhuận lớn nhất thu được sau khi giao hàng từ 3 tuyến xe đã chọn đến tất cả khách hàng của chú A.

Example

Input:
3
5 7
4 49 1 59 19 81 97 
99 82 90 99 10 58 73 
23 39 93 39 80 91 58 
59 92 16 89 57 12 3 
35 73 56 29 47 63 87 
10 9
60 56 18 45 55 44 25 100 23 
22 34 14 18 94 74 61 76 75 
86 2 23 9 96 27 21 92 89 
30 73 78 94 9 55 23 77 38 
17 4 91 13 90 54 80 100 23 
3 3 70 55 30 35 39 75 27 
64 35 73 49 54 4 8 19 34 
38 96 80 62 45 60 62 8 77 
73 46 93 73 29 97 12 36 36 
30 17 33 57 59 50 21 97 25 
8 21
55 6 20 80 27 89 14 62 22 1 24 85 91 41 57 97 98 3 45 27 34 
73 5 50 1 27 39 93 51 23 46 40 58 74 7 84 100 94 76 36 55 53 
64 70 22 57 14 53 97 68 91 8 3 23 22 22 73 37 91 48 86 73 44 
48 81 7 9 59 99 58 46 65 54 64 73 7 48 54 86 26 68 40 71 55 
82 15 48 50 1 7 87 22 2 19 92 60 66 50 6 44 52 57 25 37 88 
59 35 1 59 64 72 40 36 76 67 87 6 26 70 80 19 56 97 40 77 78 
30 82 83 11 47 34 6 38 60 68 60 85 67 98 25 90 85 15 56 95 87 
38 68 75 92 2 32 29 13 11 44 41 42 53 9 17 67 3 30 90 75 11

Output:
#1 641
#2 784
#3 1711