Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3627
Treasure Hunt II

Time Limit: 2 Seconds      Memory Limit: 65536 KB

There are n cities(1, 2, ... ,n) forming a line on the wonderland. city i and city i+1 are adjacent and their distance is 1. Each city has many gold coins. Now, Alice and her friend Bob make a team to go treasure hunting. They starts at city p, and they want to get as many gold coins as possible in T days. Each day Alice and Bob can move to adjacent city or just stay at the place, and their action is independent. While as a team, their max distance can't exceed M.

Input

The input contains multiple cases.
The first line of each case are two integers n, p as above.
The following line contain n interger,"v1 v2 ... vn" indicate the gold coins in city i.
The next line is M, T.
(1<=n<=100000, 1<=p<=n, 0<=vi<=100000, 0<=M<=100000, 0<=T<=100000)

Output

Output the how many gold coins they can collect at most.

Sample Input

6 3
1 2 3 3 5 4
2 1

Sample Output

8

Hint

At day 1: Alice move to city 2, Bob move to city 4.

They can always get the gold coins of the starting city, even if T=0


Author: LI, Chao
Contest: ZOJ Monthly, July 2012
Submit    Status