Geometry

View as PDF

Submit solution

Points: 100
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

Problem Description

Josh loves competitive programming and normally gets some enjoyment out of solving problems. However, Josh hates geometry problems, because they make him horribly depressed.

Tonight's Codeforces contest can be modeled as an array of n integers, where the ith value of the array is a positive integer representing the enjoyment he will gain from solving the ith problem. The exception to this rule is geometry problems, of which there will likely be some. These are represented by the value -999999999.

Josh knows that he only has time for k problems and only wants to do consecutive problems. Given the array of enjoyments a, what is the largest sum of up to k consecutive values?

Input Format

The first line of the input will be two integers, n and k. The next line of the input will consist of n integers, representing a.

Output Format

Output a single integer, the maximum sum of a subarray of a that is length k.

Constraints

n \le 1e5

k \le n

1 \le a[i] \le 1e3

Sample Input 1

5 3
-999999999  3 1 4 -999999999

Sample Output 1

8

Sample Input 2

10 4
289 -999999999 648 178 18 213 514 771 350 312

Sample Output 2

1947

Comments

There are no comments at the moment.