### PROBLEM LINK:

**Author:** Sergey Kulik

**Tester:** Misha Chorniy

**Editorialist:** Pawel Kacprzak

### DIFFICULTY:

CAKEWALK

### PREREQUISITES:

None

### PROBLEM:

Given availability of 3 types of leaves and availability of 3 different colors for each type of a leaf find out what is the maximum number of leaves that can be chosen in such a way that all chosen leaves are of the same type or of the same color and the number of chosen leaves is odd. If there is no way to choose the leaves according to these rules, then answer is 0. In one test file there are multiple test cases to handle.

### QUICK EXPLANATION:

First, for each type of leaves calculate the result when only leaves of this type are chosen. Next, for each color of leaves also calculate the result when only leaves of this color are chosen. Since there are 3 types and 3 colors, then the final result is the maximum from these total 6 possibilities.

### EXPLANATION:

### Subtask 1

In the first subtask there are at most 5 leaves of any type and color in any test case. This allows some solutions taking advantage of this fact to pass test cases with such low constraints. On can for example try to iterate over all possible sizes of the resulting bouquet and for each such size decide if it is possible to create it.

### Subtask 2

In the second subtask there are up to 10^9 leaves of any type and color, however, the task is still very easy. Since in the result all leaves has to have the same type or the same color (both type and color are also valid), we can iterate over all types first and for each type, sum up all the leaves of this type and subtract 1 from this sum if it is even (because we want the number of chosen leaves to be odd). After that, we can do the same with color, i.e. iterate over all colors and for each color sum up all the leaves of this color and subtract 1 from this sum if it is even. The final result is the maximum from these 6 values computed this way.

Let c[i][j] denotes the number of leaves from the i-th type and the j-th. The below pseudocode illustrates the approach:

```
res = 0
for i = 1 to 3:
subres = c[i][1] + c[i][2] + c[i][3]
if subres % 2 == 0
subres = subres - 1
res = max(res, subres)
for j = 1 to 3:
subres = c[1][j] + c[2][j] + c[3][j]
if subres % 2 == 0
subres = subres - 1
res = max(res, subres)
print res
```

Last but not least, be aware that the result can be bigger than 32-bit integer.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution will be posted soon.

Tester’s solution can be found here.

Editorialist’s solution can be found here.