TopCoder

aacpschool

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

75.0% (3/4)

Description

本題改編自 2016 年 10 月 APCS 考古題。

玫瑰班的小孩們喜歡吃糖果，他們想比賽誰能從家裡帶來最大的糖果袋。一共有 $N$ 個小孩加入比賽，且每個小孩家裡都各有 $M$ 個容量不一的糖果袋。在第二天，這 $N$ 個小孩會從家裡選出最大的糖果袋裝滿糖果並帶來班上。此外還有一個特別規則，如果一個糖果袋容量整除現場總糖果數，那該糖果袋會被加冕為完美糖果袋。

請你求出帶來班上的一共有幾個糖果，並且有哪些糖果袋是完美糖果袋。

Input Format

輸入第一行是兩個空白分隔的數字 $N, M$，分別代表參戰人數和每人家中有多少糖果袋。

接著有 $N$ 行每行 $M$ 個空白分隔的數字 $a_{ij}$，第 $i$ 行代表第 $i$ 個人家中的所有糖果袋容量（$1 \leq i \leq N$、$1 \leq j \leq M$）。

對於 $20\%$ 的輸入保證 $1\le N\le 20$，$M = 1$。
對於 $30\%$ 的輸入保證 $1\le N\le 20$，$M = 2$。
對於全部輸入保證 $1\le N, M\le 20$，$1\le a_{ij}\le 256$。

Output Format

輸出第一行是一個整數代表帶來班上的總糖果數。

第二行是所有完美糖果袋的容量，如果有多個請依照將他帶來的人的編號順序排序，數字間以空白分隔。如果沒有任何完美糖果袋，請在該行輸出 $-1$。

Sample Input 1

3 1
1
2
3

Sample Output 1

6
1 2 3

Sample Input 2

4 2
6 2
1 3
7 5
3 3

Sample Output 2

19
-1

Hints

Problem Source

APCS 歷屆

No.	Testdata Range	Constraints	Score
1	0~1	範例測資	0
2	2~10	$1\le N\le 20, M = 1$	20
3	11~22	$1\le N\le 20, M = 2$	30
4	0~32	無額外限制	50

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (VSS, KiB)	Output Limit (KiB)	Subtasks
0	1000	524288	65536	1 4
1	1000	524288	65536	1 4
2	1000	524288	65536	2 4
3	1000	524288	65536	2 4
4	1000	524288	65536	2 4
5	1000	524288	65536	2 4
6	1000	524288	65536	2 4
7	1000	524288	65536	2 4
8	1000	524288	65536	2 4
9	1000	524288	65536	2 4
10	1000	524288	65536	2 4
11	1000	524288	65536	3 4
12	1000	524288	65536	3 4
13	1000	524288	65536	3 4
14	1000	524288	65536	3 4
15	1000	524288	65536	3 4
16	1000	524288	65536	3 4
17	1000	524288	65536	3 4
18	1000	524288	65536	3 4
19	1000	524288	65536	3 4
20	1000	524288	65536	3 4
21	1000	524288	65536	3 4
22	1000	524288	65536	3 4
23	1000	524288	65536	4
24	1000	524288	65536	4
25	1000	524288	65536	4
26	1000	524288	65536	4
27	1000	524288	65536	4
28	1000	524288	65536	4
29	1000	524288	65536	4
30	1000	524288	65536	4
31	1000	524288	65536	4
32	1000	524288	65536	4

712 . 分糖果