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,"*v*_{1} *v*_{2} ... *v*_{n}" indicate the gold coins in city *i*.

The next line is M, T.

(*1<=n<=100000*, *1<=p<=n*, *0<=v*_{i}<=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**
Submit
Status