Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3628
Treasure Hunt III

Time Limit: 2 Seconds      Memory Limit: 65536 KB

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 ).
In each test case, first there are 3 integers, n, T, S ( 1 <= n, T, S <=50000 ). The index of Rooms starts from 1, and S is in the range of 1 to n.
Then there is a line containing n non-negtive integers with the ith integer indicating the number of gold in the ith room. All these integers are no more than 10^9.

Output

For each case, output one line with an integer which is the maximum gold Alice can collect.

Sample Input

4 1 2
3 4 5 6

Sample Output

5

Hint

In 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
Submit    Status