Mr. Chanek is currently participating in a science fair that is popular in town. He finds an exciting puzzle in the fair and wants to solve it.

There are $N$ atoms numbered from $1$ to $N$. These atoms are especially quirky. Initially, each atom is in normal state. Each atom can be in an excited. Exciting atom $i$ requires $D_i$ energy. When atom $i$ is excited, it will give $A_i$ energy. You can excite any number of atoms (including zero).

These atoms also form a peculiar one-way bond. For each $i$, $(1 \le i < N)$, if atom $i$ is excited, atom $E_i$ will also be excited at no cost. Initially, $E_i$ = $i+1$. Note that atom $N$ cannot form a bond to any atom.

Mr. Chanek must change exactly $K$ bonds. Exactly $K$ times, Mr. Chanek chooses an atom $i$, $(1 \le i < N)$ and changes $E_i$ to a different value other than $i$ and the current $E_i$. Note that an atom's bond can remain unchanged or changed more than once. Help Mr. Chanek determine the maximum energy that he can achieve!

note: You must first change exactly $K$ bonds before you can start exciting atoms.


-----Input-----

The first line contains two integers $N$ $K$ $(4 \le N \le 10^5, 0 \le K < N)$, the number of atoms, and the number of bonds that must be changed.

The second line contains $N$ integers $A_i$ $(1 \le A_i \le 10^6)$, which denotes the energy given by atom $i$ when on excited state.

The third line contains $N$ integers $D_i$ $(1 \le D_i \le 10^6)$, which denotes the energy needed to excite atom $i$.


-----Output-----

A line with an integer that denotes the maximum number of energy that Mr. Chanek can get.


-----Example-----
Input
6 1
5 6 7 8 10 2
3 5 6 7 1 10

Output
35



-----Note-----

An optimal solution to change $E_5$ to 1 and then excite atom 5 with energy 1. It will cause atoms 1, 2, 3, 4, 5 be excited. The total energy gained by Mr. Chanek is (5 + 6 + 7 + 8 + 10) - 1 = 35.

Another possible way is to change $E_3$ to 1 and then exciting atom 3 (which will excite atom 1, 2, 3) and exciting atom 4 (which will excite atom 4, 5, 6). The total energy gained by Mr. Chanek is (5 + 6 + 7 + 8 + 10 + 2) - (6 + 7) = 25 which is not optimal.

Difficulty: interview

Starter code:

Solutions:
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
d = list(map(int, input().split()))

if k == 0:
    best = 0
    curr = sum(a)
    for i in range(n):
        best = max(best, curr - d[i])
        curr -= a[i]
    print(best)
elif k == 1:
    best = sum(a[:-1]) - min(d[:-1])
    
    other = sum(a)
    other -= sorted(d)[0]
    other -= sorted(d)[1]

    curr = sum(a)
    for i in range(n):
        if i:
            best = max(best, curr - d[i])
        curr -= a[i]

    o2 = sum(a) - min(a[1:]) - d[0]
    
    print(max((best,other,0, o2)))
else:
    print(max((sum(a) - min(d[:-1]),0,a[-1] - d[-1])))


N,K = map(int,input().split())
A = list(map(int,input().split()))
D = list(map(int,input().split()))
if K >= 2:
    print(max(0,sum(A)-min(D[:N-1]),A[N-1]-D[N-1]))
if K == 0:
    S = 0
    ans = 0
    for i in range(N)[::-1]:
        S += A[i]
        ans = max(ans,S-D[i])
    print(ans)
if K == 1:
    minD = [D[0]]
    csA = [A[0]]
    for i in range(1,N):
        minD.append(min(minD[-1],D[i]))
        csA.append(csA[-1]+A[i])
    csinvA = [A[N-1]]
    for i in range(N-1)[::-1]:
        csinvA.append(csinvA[-1]+A[i])
    csinvA = csinvA[::-1]
    right = []
    S = 0
    for i in range(N)[::-1]:
        S += A[i]
        right.append(S-D[i])
    right = right[::-1]
    rightM = [right[N-1]]
    for i in range(N-1)[::-1]:
        rightM.append(max(rightM[-1],right[i]))
    rightM = rightM[::-1]
    ans = 0
    z = 0
    for i in range(N)[::-1]:
        x = 0
        y = csA[i]-minD[i]
        if y >= 0:
            x += y
        x += z
        if i != N-1 and i != 0:
            ans = max(ans,x)
        z = max(z,right[i])
    for i in range(N-2):
        ans = max(ans,right[i+1])
        ans = max(ans,rightM[0]-D[i+1])
        ans = max(ans,rightM[i+2])
        ans = max(ans,rightM[0]-A[i+1])
    print(ans)

import heapq
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
b=list(map(int,input().split()))
s=sum(a)
pre=[0]
j=0
while(j<n):
    pre.append(a[j]+pre[-1])
    j+=1
ab=[]
af=[]
af1=[]
j=n-1
while(j>=0):
    heapq.heappush(af,-(s-pre[j]-b[j]))
    af1.append(-af[0])

    j+=-1
af1.reverse()
if k==0:
    j=0
    ans=0
    while(j<n):
        ans=max(ans,s-pre[j]-b[j])
        j+=1
    print(ans)

elif k==1:
    j=0
    m=float("inf")
    ans=0
    while (j < (n - 1)):
        m=min(m,b[j])
        if j<(n-2):
            ans = max(ans, max(0,pre[j + 1] - m) + max(0, af1[j + 1]), s - pre[j] - b[j] - a[j + 1],s-b[0]-a[j+1])
        else:
            ans = max(ans, pre[j + 1] - m + max(0, af1[j + 1]), s - pre[j] - b[j] - a[j + 1])


        j += 1
    j=0
    while(j<(n-1)):
        ans=max(ans,s-a[-1]-b[j]+max(0,a[-1]-b[-1]))

        j+=1
    print(ans)
else:
    j=0
    ans=0
    while(j<(n-1)):
        ans=max(ans,s-b[j])

        j+=1
    ans=max(ans,a[-1]-b[-1])
    print(ans)









import heapq
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
b=list(map(int,input().split()))
s=sum(a)
pre=[0]
j=0
while(j<n):
    pre.append(a[j]+pre[-1])
    j+=1
ab=[]
af=[]
af1=[]
j=n-1
while(j>=0):
    heapq.heappush(af,-(s-pre[j]-b[j]))
    af1.append(-af[0])

    j+=-1
af1.reverse()
if k==0:
    j=0
    ans=0
    while(j<n):
        ans=max(ans,s-pre[j]-b[j])
        j+=1
    print(ans)

elif k==1:
    j=0
    m=float("inf")
    ans=0
    while (j < (n - 1)):
        m=min(m,b[j])
        if j<(n-2):
            ans = max(ans, max(0,pre[j + 1] - m) + max(0, af1[j + 1]), s - pre[j] - b[j] - a[j + 1],s-b[0]-a[j+1])
        else:
            ans = max(ans, pre[j + 1] - m + max(0, af1[j + 1]), s - pre[j] - b[j] - a[j + 1])


        j += 1
    j=0
    while(j<(n-1)):
        ans=max(ans,s-a[-1]-b[j]+max(0,a[-1]-b[-1]))

        j+=1
    print(ans)
else:
    j=0
    ans=0
    while(j<(n-1)):
        ans=max(ans,s-b[j])

        j+=1
    ans=max(ans,a[-1]-b[-1])
    print(ans)









n, k = map(int, input().split())
a = list(map(int, input().split()))
d = list(map(int, input().split()))

if k == 0:
    best = 0
    curr = sum(a)
    for i in range(n):
        best = max(best, curr - d[i])
        curr -= a[i]
    print(best)
elif k == 1:
    best = sum(a[:-1]) - min(d[:-1])
    
    other = sum(a)
    other -= sorted(d)[0]
    other -= sorted(d)[1]

    curr = sum(a)
    for i in range(n):
        if i:
            best = max(best, curr - d[i])
        curr -= a[i]

    o2 = sum(a) - min(a[1:]) - d[0]
    
    print(max((best,other,0, o2)))
else:
    print(max((sum(a) - min(d[:-1]),0,a[-1] - d[-1])))

n, k = map(int, input().split());a = list(map(int, input().split()));d = list(map(int, input().split()))
if k == 0:
    best = 0;curr = sum(a)
    for i in range(n):best = max(best, curr - d[i]);curr -= a[i]
    print(best)
elif k == 1:
    best = sum(a[:-1]) - min(d[:-1]);other = sum(a);other -= sorted(d)[0];other -= sorted(d)[1];curr = sum(a)
    for i in range(n):
        if i:best = max(best, curr - d[i])
        curr -= a[i]
    o2 = sum(a) - min(a[1:]) - d[0];print(max((best,other,0, o2)))
else:print(max((sum(a) - min(d[:-1]),0,a[-1] - d[-1])))

N, K = map(int, input().split())
A = list(map(int, input().split()))
D = list(map(int, input().split()))

suf_min = [None]*N
suf_min[-1] = A[-1]
suf_sum = [None]*N
suf_sum[-1] = A[-1]
suf_ans = [None]*N
suf_ans[-1] = max(A[-1] - D[-1], 0)
for i in range(N-2, -1, -1):
    suf_min[i] = min(A[i], suf_min[i+1])
    suf_sum[i] = suf_sum[i+1] + A[i]
    suf_ans[i] = max(suf_ans[i+1], suf_sum[i]-D[i])
    # print(i, suf_ans[i])

if K >= 2:
    print(max(0, sum(A) - min(*D[:-1]), suf_ans[0]))
    return

if K == 0:
    print(max(suf_ans[0], 0))
    return

pre_min = D[0]
pre_sum = 0
ans = max(0, sum(A) - D[0] - suf_min[0])
for i in range(N-1):
    pre_sum += A[i]
    pre_min = min(pre_min, D[i])
    ans = max(ans, pre_sum - pre_min + suf_ans[i+1], suf_ans[i+1])
print(max(0, ans))

import sys
n, k = list(map(int, input().split(' ')))


activate = list(map(int, input().split(' ')))
deactivate = list(map(int, input().split(' ')))

presum = [0 for _ in range(n+2)]

for i in range(1, n+1):
    presum[i] = presum[i-1] + activate[i-1]

ret = 0

if k == 0:
    for i in range(1, n+1):
        ret = max(ret, presum[n] - presum[i-1] - deactivate[i-1])
elif k == 1:
    for i in range(1, n):
        ret = max(ret, presum[n-1] - deactivate[i-1])
    
    if deactivate[n-1] < activate[n-1]:
        ret += (activate[n-1] - deactivate[n-1])

    deac = sorted(deactivate[1:n-1])
    ac = sorted(activate[1:n-1])

    ret = max(ret, presum[n] - deac[0] - deac[1])
    ret = max(ret, presum[n] - deactivate[0] - ac[0])
    ret = max(ret, presum[n] - deactivate[0] - deac[0])
    
    for i in range(2, n+1):
        ret = max(ret, presum[n] - presum[i-1] - deactivate[i-1])
else:
    for i in range(1, n):
        ret = max(ret, presum[n] - deactivate[i-1])   

    ret = max(ret, activate[n-1] - deactivate[n-1])

print(ret)

n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
d = list(map(int, input().split()))

if k >= 2:
    m = min(d[: -1])
    print(max(sum(a) - m, a[-1] - d[-1], 0))
elif k == 0:
    rightans = [0] * n
    cursum = 0
    ans = 0
    for i in range(n - 1, -1, -1):
        cursum += a[i]
        rightans[i] = max(cursum - d[i], 0)
    print(max(rightans))
else:
    leftd = int(1e9)
    leftsum = 0
    rightans = [0] * n
    cursum = 0
    ans = 0
    for i in range(n - 1, -1, -1):
        cursum += a[i]
        rightans[i] = max(cursum - d[i], 0)
    for i in range(n - 1, 0, -1):
        rightans[i - 1] = max(rightans[i - 1], rightans[i])
    for i in range(n - 1):
        leftd = min(leftd, d[i])
        leftsum += a[i]
        curans = max(leftsum - leftd, 0) + rightans[i + 1]
        ans = max(ans, curans)

    cursum = 0
    rightmin = int(1e9)
    for i in range(n - 1, -1, -1):
        cursum += a[i]
        ans = max(ans, cursum - rightmin - d[i])
        rightmin = min(rightmin, a[i])
    print(ans)


import sys

n, k = list(map(int, input().split(' ')))

activate = list(map(int, input().split(' ')))
deactivate = list(map(int, input().split(' ')))

presum = [0 for _ in range(n + 2)]

for i in range(1, n + 1):
    presum[i] = presum[i - 1] + activate[i - 1]

ret = 0

if k == 0:
    for i in range(1, n + 1):
        # 情况0，不需要考虑连带
        ret = max(ret, presum[n] - presum[i - 1] - deactivate[i - 1])
elif k == 1:
    for i in range(1, n):
        # 情况3 n-1连1
        ret = max(ret, presum[n - 1] - deactivate[i - 1])

    # 情况3再加上第N个离子
    if deactivate[n - 1] < activate[n - 1]:
        ret += (activate[n - 1] - deactivate[n - 1])

    deac = sorted(deactivate[1:n - 1])
    ac = sorted(activate[1:n - 1])

    # 情况5，激活1，跳过1个节点
    ret = max(ret, presum[n] - deactivate[0] - ac[0])
    # 情况6 激活1，跳过1个节点后，再激活
    ret = max(ret, presum[n] - deactivate[0] - deac[0])
    # 情况4
    ret = max(ret, presum[n] - deac[0] - deac[1])

    # 情况7 1连n，激活i
    for i in range(2, n + 1):
        ret = max(ret, presum[n] - presum[i - 1] - deactivate[i - 1])
else:
    # 情况1
    for i in range(1, n):
        ret = max(ret, presum[n] - deactivate[i - 1])

        # 情况2
    ret = max(ret, activate[n - 1] - deactivate[n - 1])

print(ret)

import sys

n, k = list(map(int, input().split(' ')))

activate = list(map(int, input().split(' ')))
deactivate = list(map(int, input().split(' ')))

presum = [0 for _ in range(n + 2)]

for i in range(1, n + 1):
    presum[i] = presum[i - 1] + activate[i - 1]

ret = 0

if k == 0:
    for i in range(1, n + 1):
        # 情况0，不需要考虑连带
        ret = max(ret, presum[n] - presum[i - 1] - deactivate[i - 1])
elif k == 1:
    for i in range(1, n):
        # 情况3 n-1连1
        ret = max(ret, presum[n - 1] - deactivate[i - 1])

    # 情况3再加上第N个离子
    if deactivate[n - 1] < activate[n - 1]:
        ret += (activate[n - 1] - deactivate[n - 1])

    deac = sorted(deactivate[1:n - 1])
    ac = sorted(activate[1:n - 1])

    # 情况5，激活1，跳过1个节点
    ret = max(ret, presum[n] - deactivate[0] - ac[0])
    # 情况6 激活1，跳过1个节点后，再激活
    ret = max(ret, presum[n] - deactivate[0] - deac[0])
    # 情况4
    ret = max(ret, presum[n] - sorted(deactivate[0:n - 1])[0] - sorted(deactivate[0:n - 1])[1])

    # 情况7 1连n，激活i
    for i in range(2, n + 1):
        ret = max(ret, presum[n] - presum[i - 1] - deactivate[i - 1])
else:
    # 情况1
    for i in range(1, n):
        ret = max(ret, presum[n] - deactivate[i - 1])

        # 情况2
    ret = max(ret, activate[n - 1] - deactivate[n - 1])

print(ret)

import sys

n, k = list(map(int, input().split(' ')))

activate = list(map(int, input().split(' ')))
deactivate = list(map(int, input().split(' ')))

presum = [0 for _ in range(n + 2)]

for i in range(1, n + 1):
    presum[i] = presum[i - 1] + activate[i - 1]

ret = 0

if k == 0:
    for i in range(1, n + 1):
        # 情况0，不需要考虑连带
        ret = max(ret, presum[n] - presum[i - 1] - deactivate[i - 1])
elif k == 1:
    for i in range(1, n):
        # 情况3 n-1连1
        ret = max(ret, presum[n - 1] - deactivate[i - 1])

    # 情况3再加上第N个离子
    if deactivate[n - 1] < activate[n - 1]:
        ret += (activate[n - 1] - deactivate[n - 1])

    deac = sorted(deactivate[0:n - 1])
    ac = sorted(activate[1:n - 1])

    # 情况5，激活1，跳过1个节点
    ret = max(ret, presum[n] - deactivate[0] - ac[0])
    # 情况4
    ret = max(ret, presum[n] - deac[0] - deac[1])

    # 情况7 1连n，激活i
    for i in range(2, n + 1):
        ret = max(ret, presum[n] - presum[i - 1] - deactivate[i - 1])
else:
    # 情况1
    for i in range(1, n):
        ret = max(ret, presum[n] - deactivate[i - 1])

        # 情况2
    ret = max(ret, activate[n - 1] - deactivate[n - 1])

print(ret)

import sys

n, k = list(map(int, input().split(' ')))

activate = list(map(int, input().split(' ')))       # 释放的能量
deactivate = list(map(int, input().split(' ')))     # 需求的能量
ls = list(zip(activate[0:-1], deactivate[0:-1]))
diff = ls[0][0] - ls[0][1]

presum = [0 for _ in range(n + 2)]

for i in range(1, n + 1):
    presum[i] = presum[i - 1] + activate[i - 1]

ret = 0

if k == 0:
    for i in range(1, n + 1):
        # 情况0，不需要考虑连带
        ret = max(ret, presum[n] - presum[i - 1] - deactivate[i - 1])
elif k == 1:

    ret = max(ret, presum[n - 1] - min(deactivate), presum[n] - min(deactivate) - deactivate[n - 1])

    deac = sorted(deactivate[0:n - 1])
    ac = sorted(activate[1:n - 1])

    # 情况5，激活1，跳过1个节点
    ret = max(ret, presum[n] - deactivate[0] - ac[0])
    # 情况4
    ret = max(ret, presum[n] - deac[0] - deac[1])

    # 情况7 1连n，激活i
    for i in range(2, n + 1):
        ret = max(ret, presum[n] - presum[i - 1] - deactivate[i - 1])
else:
    # 情况1
    for i in range(1, n):
        ret = max(ret, presum[n] - deactivate[i - 1])

        # 情况2
    ret = max(ret, activate[n - 1] - deactivate[n - 1])

print(ret)


n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
d = list(map(int, input().split()))
pref=[0]
for i in range(n):
    pref.append(pref[-1]+a[i])
if k==0:
    ans=0
    for i in range(1,n+1):
        ans=max(ans,pref[-1]-pref[i-1]-d[i-1])
    print(ans)
elif k == 1:
    best = sum(a[:n-1]) - min(d[:n-1])
    
    other = sum(a)
    other -= sorted(d)[0]
    other -= sorted(d)[1]
 
    curr = sum(a)
    for i in range(n):
        if i:
            best = max(best, curr - d[i])
        curr -= a[i]
 
    o2 = sum(a) - min(a[1:]) - d[0]
    
    print(max((best,other,0, o2)))
else:
    print(max((sum(a) - min(d[:-1]),0,a[-1] - d[-1])))