Sampling numbers for maximum sum divisible by 4
Problem
There is a data set consisting of triples of natural numbers. It is necessary to choose two numbers from each triple so that the sum of all the chosen numbers is a multiple of 4 and at the same time is the maximum possible. If it is impossible to get the required amount, return 0 as an answer.
Input
The input to the program in the first line is the number of triples N (\(1 <= N <= 100000\)). Each of the following N lines contains three natural numbers not exceeding 10,000.
Imprint
Output the answer to the problem
Examples
| # |
Input |
Output |
| 1 |
6
8 3 4
4 8 12
9 5 6
2 8 3
12 3 5
1 4 12
|
88 |