Title description:
"Angry birds" game, you always played fairy's house, as the saying goes: "the higher you fly, hit a more malicious", all the birds in the game was demonstrated to fly higher, even death, but beg good leave earth,
In order to get higher rates of flying height, the birds do not know where to get a batch of divine power tonic pill, ate these pills will help the birds sleep on a higher altitude, unfortunately, I don't know let the cat out of the bag that damned traitor, evil green pigs got the information, so they bribed a local wizard, hope wizard throws a difficult birds, so the wizard overnight in this batch of pill on the sleep imposed a terrible curse, is the birds in taking these pills, sleep when eating to fill an odd number of big pill will increase flight capability (added value for the large fill pill "hiding" value); Eating to fill an even number of big pill can reduce flight capability (lower value is the tonic pill "hiding" value), and of course the birds can skip when choosing some pills don't eat, sleep a little puzzled the birds, although said that as long as careful selection can be eaten to ensure that this batch of big fill after pill can get capability of ascension, but wonder tonic pill is called divine power, it took that's high price is very not easy to make in one's hand, how can casually dealing with settles, is there an option you can tell this batch of divine power tonic pill maximum effectiveness?
Fortunately, the birds have a friend when programmers, also is you, they now turn to you, then you can find an option to fill this batch of divine power big pill the effect best?
Input:
How much input group use cases, the use cases in each group:
Line 1: an integer n (1 & lt;=n<=150000), says the number of big supplement pills
Line 2: contains n integers PI (1 & lt;=pi<=500), and each integer is a tonic pill "hiding" value, assuming that the birds can fill the order of the according to the given by picking big pills,
Output:
Line 1: an integer, edible this batch of divine power after the big tonic capsule can achieve maximum efficacy,
Input the sample:
8
7 8, 1 2 3 4 5 6
12
51, 141, 41, 152, 79, 72, 28 145 41 26, 176, 78
The output sample:
17
519
CodePudding user response:
Dp2 dp1 [I], [I] 0 & lt;=I & lt;=nDp1 eat first j a, and have already had an odd number, the most massive
Dp2 eat first j a, and has had an even number of get maximum
The equation of state in this way, it was clear