Small Locomotives

A train is normally pulled by one locomotive at the front. If that locomotive breaks down, the train cannot continue, so three small locomotives are kept ready at some stations. A small locomotive can pull far fewer passenger cars than the regular locomotive.

When the regular locomotive breaks down, the three small locomotives cannot pull every car. The cars to be pulled are chosen by the following rules.

1. A maximum number of cars that one small locomotive can pull is fixed in advance. No small locomotive may pull more than this number, and all three small locomotives have the same limit.
2. The total number of passengers carried by the three small locomotives must be as large as possible. The number of passengers in each car is known, and passengers cannot move to other cars.
3. Each small locomotive must pull cars with consecutive numbers. Cars are numbered 1, 2, ... starting from the car directly behind the locomotive.

For example, suppose the train has 7 cars and each small locomotive can pull at most 2 cars. The table below gives the number of passengers in cars 1 through 7; the number in parentheses is the car number.

If the three small locomotives pull cars 1-2, 3-4, and 6-7, they carry 240 passengers. It is impossible to carry more passengers than that.

Given the number of cars, the number of passengers in each car, and the maximum number of cars one small locomotive can pull, find the maximum number of passengers that can be carried by the three small locomotives.

The first line contains the number of cars in the train. This number is at most 50,000.

The second line contains the number of passengers in each car, from car 1 onward. Each car has at most 100 passengers, and adjacent numbers are separated by one space.

The third line contains the maximum number of cars one small locomotive can pull. This number is less than one third of the total number of cars.

Print one line containing the maximum number of passengers that can be carried by the three small locomotives.