SP20846 ISELECT - Interesting Selection

There is a giant circular container which is divided into N segments numbered from 0 to N-1. Each segment has two bottles, one is a bottle of cold-drink and other is a bottle of poision. Drinking from bottle of cold-drink increases your energy by A\[i\] while drinking from bottle of poision decreases your energy by B\[i\]. The corresponding energies for the same are given in input. Now as it is circular, so bottles in segment N-1 and segment 0 are adjacent. If you do not drink from bottle of cold-drink, then you have to drink from bottle of poision in that segment. Furthermore you cannot drink from bottle of cold-drink in adjacent segments. You have to drink in such a way so that your energy maximizes. Find this maximum value. **Note : Your initial energy will be 0 and the final maximum energy can be negative.** **Input Format** There will be T test cases and in each test case there will be an integer N which is the size of the container. Next line contain N integers denoting the first array and the second line also contain N integers denoting the second array. **Output Format** There will be T lines each containing the output for each test case. **Constraints** 1 1 1 9 **Sample Input** 1 3 1 2 3 4 5 6 **Sample Output** -6 **Explanation** There are 3 segments and the pairs are (1,4), (2,5) ,(3,6) The optimal solution is to drink third potion and first two bottle of poision. The answer in this case is (-4 + - 5 + 3 ) = -6

N/A

N/A