Maximum Sum (APCS 2016-10 Intermediate)

You are given \(N\) groups of numbers, each containing exactly \(M\) positive integers. Choose one number from every group. If the number chosen from group \(i\) is \(t_i\), their sum is

First maximize \(S\). Then determine which chosen numbers divide \(S\).

Input Format

The first line contains two positive integers \(N\) and \(M\).

Each of the next \(N\) lines contains \(M\) positive integers representing one group.

Constraints

• \(1 \le N \le 20\)
• \(1 \le M \le 20\)
• Every input number \(x\) satisfies \(1 \le x \le 256\).
• All input values are integers.

Output Format

Print the maximum sum \(S\) on the first line.

On the second line, in group order, print every chosen number that divides \(S\). Separate adjacent numbers by one space and do not print trailing spaces.

If none of the chosen numbers divides \(S\), print -1 on the second line.

Only numbers actually chosen from their groups are checked. If the same value is chosen from different groups, print it once for each such group. Output is judged by exact match.

Scoring

The two samples are judged but worth zero points. There are exactly \(20\) scored groups worth \(5\) points each:

• Groups \(1\)–\(4\) (\(20\) points): \(M=1\).
• Groups \(5\)–\(10\) (\(30\) points): \(M=2\).
• Groups \(11\)–\(20\) (\(50\) points): no additional constraints.

Sample Input 1

3 2
1 5
6 4
1 1

Sample Output 1

12
6 1

Sample Explanation 1

The chosen values are \(5,6,1\), so the maximum sum is \(S=12\). Values \(6\) and \(1\) divide \(12\), and they are printed in group order.

Sample Input 2

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

Sample Output 2

31
-1

Sample Explanation 2

The chosen values are \(6,9,7,9\), giving \(S=31\). None of them divides \(31\).

Source

APCS October 2016, implementation problem 2; adapted from ZeroJudge c295, “Maximum Sum”.