A20250407b_Google_dp

'''

lets say you are given an n array integers
task is to find the max sum you can make through your journey from 1st to last index

however at each index you can take that element and add it to your sum or leave it

but if you add it to your sum , for sure you cannot pick the next k elements to add it to your sum

-----------------------------------------------------------------------------------------------------
important thing to be noted here is -

lets solve this with dp

here at each index you have 2 choices ,and either can result in max answer

so lets make them as dp state

not take 0 and take 1

lets say

you dont want to take current element
now you are free to use the not taken dp instance of i-1 and taken dp instance of i-1

dp[i][0] = max(dp[i-1][0],dp[i-1][1])

what if

you want to take current element

you can take it but if you wanted to take it for sure last k elements might not be picked up
so you can only use prev of k elements instances before
(you cannot even use dp[i-1][0]),because you are not sure that it might be made up of dp[i-2][1]
which is i-k -1


now at i-k-1 instance you can choose taken dp instance or not taken dp instance both are allowed

so
dp[i][1] = arr[i] + max(dp[i-k-1][0],dp[i-k-1][1])


-----------------------------------------------------------------------------------------------------
input -

5 50 100 -1 -2 5 8 8
2

output -

108
'''

arr = list(map(int,input().split()))
k = int(input())

#for 0 to k-1 elements we need to run a loop to fill the states
#they wont be having i-k-1 indices so dp[i][1] for these indices will be simply arr[i]
#and again dp[i][0] is normal again which is max(dp[i-1][0],dp[i-1][1])
dp = [[0,0] for i in range(len(arr))]
lastInd = len(dp)-1
for i in range(len(arr)):
    #if i ele is taken
    if i <= k:
        dp[i][1] = arr[i]
    else:
        dp[i][1] = arr[i] + max(dp[i-k-1][0],dp[i-k-1][1])

    #if i is not taken
    if i>0:
        dp[i][0] = max(dp[i-1][0],dp[i-1][1])

# print(dp)

print(max(dp[lastInd][0],dp[lastInd][1]))