給定 N 群數字,每群都恰有 M 個正整數。若從每群數字中各選擇一個數字(假設第 i 群所選出數字為 ti),將所選出的 N 個數字加總即可得總和 S=t1+t2+⋯+tN。請寫程式計算 S 的最大值(最大總和),並判斷各群所選出的數字是否可以整除 S。
範例測資一說明:挑選的數字依序是 5,6,1,總和 S=12。而此三數中可整除 S 的是 6 與 1,6 在第二群,1 在第三群所以先輸出 6 再輸出 1。注意,1 雖然也出現在第一群,但它不是第一群中挑出的數字,所以順序是先 6 後 1。
範例測資二說明:挑選的數字依序是 6,9,7,9,總和 S=31。而此四數中沒有可整除 S 的,所以第二行輸出 -1。
-1
第一行有兩個正整數 N 和 M,1≤N≤20,1≤M≤20。 接下來的 N 行,每一行各有 M 個正整數 xi ,代表一群整數,數字與數字間有一個空格,且 1≤i≤M,以及 1≤xi≤256。
第一行輸出最大總和 S。 第二行按照被選擇數字所屬群的順序,輸出可以整除 S 的被選擇數字,數字與數字間以一個空格隔開;若 N 個被選擇數字都不能整除 S,就輸出 -1。
2016 年 APCS 考古題第 2 題「最大和」