Challenge: Best k Days

Lab Python Beginner 10 points

Read daily step counts and a number k. Print the largest total of any k days in a row, using a sliding window.

Input

Line 1: whole numbers. Line 2: k (1 ≤ k ≤ number of days).

Output

The best total.

Example

Input

2 1 5 1 3 2
3

Output

Sample input available Sample output available

Editor

Python

Hints

Add up the first k numbers.

Slide: add nums[r], subtract nums[r - k].

Solution explanation

One addition and one subtraction per step: O(n) no matter how big k is.

Show solution

nums = list(map(int, input().split()))
k = int(input())
window = sum(nums[:k])
best = window
for r in range(k, len(nums)):
    window += nums[r] - nums[r - k]
    best = max(best, window)
print(best)

Output

Answer