#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int const N = 1e5 + 10;
int n, k;
ll a[N], d[N];
ll suf[N];
ll pre[N];
int minval, minvalpos;
int mincost, mincostpos;
int main() {
  minval = (0x3f3f3f3f);
  mincost = (0x3f3f3f3f);
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
    if (i != 1 && i != n) {
      if (a[i] < minval) {
        minval = a[i];
        minvalpos = i;
      }
    }
    if (i == 1)
      pre[i] = a[i];
    else
      pre[i] = pre[i - 1] + a[i];
  }
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &d[i]);
    if (i != n) {
      if (d[i] < mincost) {
        mincost = d[i];
        mincostpos = i;
      }
    }
    suf[i] = pre[n] - pre[i - 1];
  }
  if (k >= 2) {
    printf("%lld\n", max(0LL, max(pre[n] - mincost, a[n] - d[n])));
  } else if (k == 0) {
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
      ans = max(ans, suf[i] - d[i]);
    }
    printf("%lld\n", ans);
  } else {
    ll curMinCost = (0x3f3f3f3f);
    ll cir = -(0x3f3f3f3f), li = -(0x3f3f3f3f);
    ll ans = 0LL;
    for (int i = 1; i < n; i++) {
      curMinCost = min(curMinCost, d[i]);
      cir = pre[i] - curMinCost;
      li = suf[i + 1] - d[i + 1];
      ans = max(li + cir, max(ans, max(li, cir)));
    }
    printf("%lld\n", max(0LL, max(ans, pre[n] - minval - d[1])));
  }
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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 ≤ 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 ≤ 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 ≤ N ≤ 10^5, 0 ≤ K < N), the number of atoms, and the number of bonds that must be changed.

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

The third line contains N integers D_i (1 ≤ D_i ≤ 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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int const N = 1e5 + 10;
int n, k;
ll a[N], d[N];
ll suf[N];
ll pre[N];
int minval, minvalpos;
int mincost, mincostpos;
int main() {
  minval = (0x3f3f3f3f);
  mincost = (0x3f3f3f3f);
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
    if (i != 1 && i != n) {
      if (a[i] < minval) {
        minval = a[i];
        minvalpos = i;
      }
    }
    if (i == 1)
      pre[i] = a[i];
    else
      pre[i] = pre[i - 1] + a[i];
  }
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &d[i]);
    if (i != n) {
      if (d[i] < mincost) {
        mincost = d[i];
        mincostpos = i;
      }
    }
    suf[i] = pre[n] - pre[i - 1];
  }
  if (k >= 2) {
    printf("%lld\n", max(0LL, max(pre[n] - mincost, a[n] - d[n])));
  } else if (k == 0) {
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
      ans = max(ans, suf[i] - d[i]);
    }
    printf("%lld\n", ans);
  } else {
    ll curMinCost = (0x3f3f3f3f);
    ll cir = -(0x3f3f3f3f), li = -(0x3f3f3f3f);
    ll ans = 0LL;
    for (int i = 1; i < n; i++) {
      curMinCost = min(curMinCost, d[i]);
      cir = pre[i] - curMinCost;
      li = suf[i + 1] - d[i + 1];
      ans = max(li + cir, max(ans, max(li, cir)));
    }
    printf("%lld\n", max(0LL, max(ans, pre[n] - minval - d[1])));
  }
  return 0;
}

```