
ZOJ Problem Set  3628
Alice is exploring the wonderland once again and she finds a strange house. In the house, there are n rooms which form a circle so that each room is connected to its two neighbour room. For exmaple, if Alice is in room 2, then she can go into room 1 or room 3, and if she is in room 1, she can go into room 2 or room n. In each room, there may exists some gold coins which is very valuable for Alice's wonderland trip. Every time when alice move into a room, she can choose to take the gold in the room. However, at the same time, the gold in the 2 neighbour room will disappear. For example, if Alice took the gold in room 2, and there are still gold in room 1 or room 3, then all these gold will disappear. It costs Alice 1 second to move from one room to another neighbour room. Taking gold doesn't cost any time. Since the house is going to collapse, Alice must leave the house in T seconds. At first Alice is in room S, and she can leave the house from any room. Please help Alice calculate the maximum gold she can collect in T seconds. Input
The input contains multiple test cases ( no more than 250 test cases ). OutputFor each case, output one line with an integer which is the maximum gold Alice can collect. Sample Input4 1 2 3 4 5 6 Sample Output5 HintIn the sample, Alice has just one second, and she was in room 2 at second 0, if she took the 4 gold in room 2, she cannot get any gold in the next second, but if she just move to room 3 at second 1, then she can take the 5 gold and leave the house. Author: HUANG, Qiao Contest: ZOJ Monthly, July 2012 