There is a data set consisting of triples of natural numbers. It is necessary to choose exactly one number from each triple so that the sum of all the chosen numbers is not 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.
Write an efficient program that solves the problem.
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
1 3 2
5 12 12
6 8 12
5 4 12
3 3 12
1 1 13
|
63 |