It has been five years since you founded your highly successful online restaurant Bytes and Nybbles, and you have amassed a small fortune. In need of something to do with all this money, you decide to build an extremely large and luxurious mansion.
Of course you could never live in such a mansion--you would get lost trying to find your way from one end to the other. The only purpose of this mansion would be for people to look at it and admire it. You therefore need to choose a location for your mansion so as many people can see it as possible.
Your mansion will be built on a long road, as illustrated below. One side of the road is filled with houses, each of the same size. You have done your homework, and you have a complete listing of how many people live in each house. Your mansion will cover the width of w houses combined, and will be built on the other side of this road. Your aim is to choose a location so that as many people as possible live opposite your mansion.
For instance, consider the road above and suppose that w=4. There are four possible locations for your mansion, each illustrated below. In the first location you would have 3+2+5+1=11 people living opposite. In the second location you would have 2+5+1+4=12 people opposite, and in the third and fourth locations you would have 11 and 9 people respectively. The best you can do is 12 people, and so you build your mansion in the second location (to the envy of your neighbours).
Of course this is just an example--in reality the road might be much longer, and your mansion might be much larger. Your task is to write a computer program that can choose the best location for you.
The first line of input will consist of two integers n and w, separated by a single space. The integer n represents the number of houses along the road ( 1 <= n <= 100000) and the integer w represents the width of your mansion ( 1 <= w <= n).
Following this will be n additional lines of input, giving the number of people living in each house. The ith of these lines will contain a single positive integer, giving the number of people living in the ith house. Each of these integers will be between 1 and 100 inclusive.
Your output file must consist of a single line containing a single integer, giving the largest possible number of people living opposite your mansion.
7 4 3 2 5 1 4 1 3
5 2 3 10 6 1 14
The first example input and output files above describe the scenario discussed earlier. In the second example you are given a road with n=5 houses, containing 3, 10, 6, 1 and 14 people respectively. Your mansion has width w=2, and the best possible position is opposite the second and third houses, giving a total of 10+6=16 people living across from your mansion.
The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.
Moreover, for 50% of the available marks, the input file will satisfy n <= 1000.