最大和 (APCS 2016-10 中級)

給定 \(N\) 群數字，每群都恰有 \(M\) 個正整數。若從每群數字中各選擇一個數字（假設第 \(i\) 群所選出數字為 \(t_i\)），將所選出的 \(N\) 個數字加總即可得和 \(S = t_1+t_2+\cdots+t_N\)。請寫程式計算 \(S\) 的最大值（最大總和），並判斷各群所選出的數字是否可以整除 \(S\)。

輸入格式

第一行有二個正整數 \(N\) 和 \(M\)， \(1 \le N \le 20\)，\(1 \le M \le 20\)。

接下來的 \(N\) 行，每一行各有 \(M\) 個正整數 \(x_i\)，代表一群整數，數字與數字間有一個空格，且 \(1 \le i \le M\)，以及 \(1 \le x_i \le 256\)。

輸出格式

第一行輸出最大總和 \(S\)。

第二行按照被選擇數字所屬群的順序，輸出可以整除 \(S\) 的被選擇數字，數字與數字間以一個空格隔開，最後一個數字後無空白；若 \(N\) 個被選擇數字都不能整除 \(S\)，就輸出 -1。

範例輸入 1

3 2
1 5
6 4
1 1

範例輸出 1

12
6 1

（範例一說明）挑選的數字依序是 5, 6, 1，總和 \(S=12\)。而此三數中可整除 \(S\) 的是 6 與 1，6 在第二群，1 在第 3 群所以先輸出 6 再輸出 1。注意，1 雖然也出現在第一群，但她不是第一群中挑出的數字，所以順序是先 6 後 1。

範例輸入 2

4 3
6 3 2
2 7 9
4 7 1
9 5 3

範例輸出 2

31
-1

（範例二說明）挑選的數字依序是 6,9,7,9，總和 \(S=31\)。而此四數中沒有可整除 \(S\) 的，所以第二行輸出 -1。

評分說明

輸入包含若干筆測試資料，每一筆測試資料的執行時間限制 (time limit) 均為 1 秒，依正確通過測資筆數給分。其中：

第 1 子題組 20 分： \(1 \le N \le 20\)，\(M = 1\)。

第 2 子題組 30 分： \(1 \le N \le 20\)，\(M = 2\)。

第 3 子題組 50 分： \(1 \le N \le 20\)，\(1 \le M \le 20\)。

題目來源

APCS 2016 年 10 月 29 日實作題第 2 題；題目參考 ZeroJudge c295「最大和」。

• APCS 官方歷屆試題（2016/10/29 實作題 PDF）