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: HARD
Tags: Implementation

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
(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])))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, k) = 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(1000000000.0)
	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(1000000000.0)
	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 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 >= 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(1000000000.0)
	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(1000000000.0)
	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):
		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] - deactivate[0] - ac[0])
	ret = max(ret, presum[n] - deactivate[0] - deac[0])
	ret = max(ret, presum[n] - deac[0] - deac[1])
	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) = 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])
if K >= 2:
	print(max(0, sum(A) - min(*D[:-1]), suf_ans[0]))
	exit(0)
if K == 0:
	print(max(suf_ans[0], 0))
	exit(0)
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 math
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
D = list(map(int, input().split()))

def get_suffix_sums():
	suffix_sums = [0 for i in range(N)]
	suffix_sums[N - 1] = A[N - 1]
	for i in range(N - 2, -1, -1):
		suffix_sums[i] = suffix_sums[i + 1] + A[i]
	return suffix_sums

def get_sum_minus_minimum_and_second_minimum():
	total_sum = 0
	minimum = math.inf
	second_minimum = math.inf
	for i in range(len(A)):
		total_sum += A[i]
		x = D[i]
		if x <= minimum:
			second_minimum = minimum
			minimum = x
		elif x <= second_minimum:
			second_minimum = x
	return total_sum - (minimum + second_minimum)
if K == 0:
	result = 0
	suffix_sums = get_suffix_sums()
	for i in range(N):
		result = max(result, suffix_sums[i] - D[i])
	print(result)
elif K == 1:
	result = max(0, sum(A[:-1]) - min(D[:-1])) + max(0, A[-1] - D[-1])
	suffix_sums = get_suffix_sums()
	for i in range(1, N):
		result = max(result, suffix_sums[i] - D[i])
	result = max(result, suffix_sums[0] - min(A[1:]) - D[0])
	result = max(result, get_sum_minus_minimum_and_second_minimum())
	print(result)
else:
	print(max(0, sum(A) - min(D[:-1]), 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)


(n, k) = map(int, input().split())
r = list(map(int, input().split()))
c = list(map(int, input().split()))
z = max(r[-1] - c[-1], 0)
if k == 0:
	best = z
	acc = 0
	for i in range(n - 1, -1, -1):
		acc += r[i]
		best = max(best, acc - c[i])
	print(best)
elif k > 1:
	print(max(sum(r) - min(c[:-1]), z))
else:
	best = max(z, sum(r) - sum(sorted(c)[:2]), sum(r[:-1]) - min(c[:-1]), sum(r) - min(r[1:]) - c[0])
	acc = 0
	for i in range(n - 1, 0, -1):
		acc += r[i]
		best = max(best, acc - c[i])
	print(best)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

def RL():
	return map(int, sys.stdin.readline().split())

def RLL():
	return list(map(int, sys.stdin.readline().split()))

def N():
	return int(input())

def print_list(l):
	print(' '.join(map(str, l)))
(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])))