Question
Maximal Subset Sum
You are given N sets of integers. Your task is to:
Find the
Find the
largest possible sum of integers by selecting exactly one element from each set.Input
The first line contains an integer
The next
N — the number of sets.
The next
N lines each contain integers of a set separated by spaces.Output
Print a single integer — the maximal sum achievable.
Example
Example 1:
Input
3
1 2 3
3 4 5
5 6
Output
14
Explanation:
Optimal choice: 3 (Set 1) + 5 (Set 2) + 6 (Set 3) = 14
Example 2:
Input
2
1 1
1 1
Output
2
Explanation:
Optimal choice: 1 (Set 1) + 1 (Set 2) = 2
Input
3
1 2 3
3 4 5
5 6
Output
14
Explanation:
Optimal choice: 3 (Set 1) + 5 (Set 2) + 6 (Set 3) = 14
Example 2:
Input
2
1 1
1 1
Output
2
Explanation:
Optimal choice: 1 (Set 1) + 1 (Set 2) = 2