# zoj 3627 F – Treasure Hunt II(贪心)

Time Limit:2000MS     Memory Limit:65536KB     64bit IO Format:%lld & %llu

Description

There are n cities(12, … ,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 np as above.
The following line contain n interger,”v1v2 … vn” indicate the gold coins in city i.
The next line is M, T.
(1<=n<=1000001<=p<=n0<=vi<=1000000<=M<=1000000<=T<=100000)

Output

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

Sample Input

Sample Output

#### 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

View Code

Posted in ACM