Cần chuyển hết ~n~ gói tin trên một mạng gồm ~m~ kênh truyền. Biết chi phí chuyển ~i~ gói tin trên kênh ~j~ là ~C(i,j)~ ~(1 \le C(i,j) \le 10000)~.

Yêu cầu: Cho biết một phương án chuyển gói tin với chi phí thấp nhất.

Input

Dòng 1: Hai số n và m ~(1 < n, m \le 100)~;

Dòng thứ ~i~ trong ~n~ dòng tiếp theo: Dãy ~m~ số nguyên dương ~C_1, C_2, ..., C_m~ trong đó ~C_j~ là chi phí chuyển ~i~ gói tin trên kênh ~j~.

Output

Dòng đầu tiên: Tổng chi phí thấp nhất theo phương án tìm được.

Dòng thứ ~j~ trong ~m~ dòng tiếp theo: Số lượng gói tin chuyển trên kênh ~j~.

Sample Input

5 4 2
31 10 1 1
1 31 12 13
4 10 31 1
6 1 20 19
10 5 10 10

Sample Output

2
0
4
1
0

Giải thích

Giải thích: Với ~n = 5~ gói tin, ~m = 4~ kênh và chi phí ~C(i,j)~ cho trước, trong đó ~i~ là chỉ số dòng (số gói tin), ~j~ là chỉ số cột (kênh), cách chuyển sau đây cho kết quả chi phí thấp nhất là ~2~.