The Largest Bouquet
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
It's autumn now, the time of the leaf fall.
Sergey likes to collect fallen leaves in autumn. In his city, he can find fallen leaves of maple, oak and poplar. These leaves can be of three different colors: green, yellow or red.
Sergey has collected some leaves of each type and color. Now he wants to create the biggest nice bouquet from them. He considers the bouquet nice iff all the leaves in it are either from the same type of tree or of the same color (or both). Moreover, he doesn't want to create a bouquet with even number of leaves in it, since this kind of bouquets are considered to attract bad luck. However, if it's impossible to make any nice bouquet, he won't do anything, thus, obtaining a bouquet with zero leaves.
Please help Sergey to find the maximal number of leaves he can have in a nice bouquet, which satisfies all the above mentioned requirements.
Please note that Sergey doesn't have to use all the leaves of the same color or of the same type. For example, if he has 20 maple leaves, he can still create a bouquet of 19 leaves.
IThe first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows."
The first line of each test case contains three space-separated integers MG MY MR denoting the number of green, yellow and red maple leaves respectively.
The second line contains three space-separated integers OG OY OR denoting the number of green, yellow and red oak leaves respectively.
The third line of each test case contains three space-separated integers PG PY PR denoting the number of green, yellow and red poplar leaves respectively.
For each test case, output a single line containing the maximal amount of flowers in nice bouquet, satisfying all conditions or 0 if it's impossible to create any bouquet, satisfying the conditions.
- 1 ≤ T ≤ 10000
- Subtask 1 (50 points): 0 ≤ MG, MY, MR, OG, OY, OR, PG, PY, PR ≤ 5
- Subtask 2 (50 points): 0 ≤ MG, MY, MR, OG, OY, OR, PG, PY, PR ≤ 109
Input: 1 1 2 3 3 2 1 1 3 4 Output: 7
Example case 1. We can create a bouquet with 7 leaves, for example, by collecting all yellow leaves. This is not the only way to create the nice bouquet with 7 leaves (for example, Sergey can use all but one red leaves), but it is impossible to create a nice bouquet with more than 7 leaves.
|Tags||cakewalk, ltime41, xcwgf666|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.