Window of length L with maximum sum

Mobile coding works. A laptop is faster for long sessions.

Problem

Read two positive natural numbers n and L with L <= n, then n integers forming a sequence v[1], v[2], ..., v[n]. Find the contiguous subarray of exactly L elements whose sum is greatest.

Because dividing by L preserves order, a window of length L with the greatest sum also has the greatest average, so the problem is equivalent to finding the fixed-length window of maximum average.

Print the position of the first element of that window (numbered from 1) and the value of the sum. If there are several windows of length L with the same maximum sum, choose the first.

Input format

Input input.txt

The first line contains two natural numbers `n` and `L` separated by a space. The second line contains `n` integers separated by spaces. - `1 <= L <= n <= 1000` - `-1000 <= v[i] <= 1000` - use the sliding-window technique for efficiency

Output format

Output output.txt

Print two numbers separated by a space: the position of the first element of the maximum-sum window, and the value of that sum. The line ends with a newline character.

Example

input

6 3

1 2 3 4 5 6

output

4 15

Sample cases (from the problem)

Sample Case 1

Input

6 3

1 2 3 4 5 6

Expected output

4 15

Ready to solve this challenge?

Create a free account to write code, submit solutions, and track your progress.

🔍 Interactive Debugger

0 / 0

Analyzing your code...

Problem

Input format

Output format

Example

Stuck?

💬 Discussion

Sample cases (from the problem)

Solve it your way first

Ready to solve this challenge?

🔍 Interactive Debugger

Error

Problem

Input format

Output format

Example

Stuck?

💬 Discussion

Sample cases (from the problem)

Solve it your way first

Ready to solve this challenge?

⌨️ Keyboard Shortcuts

🔍 Interactive Debugger

Error