#include <bits/stdc++.h>
const int maxn = 500005, maxt = maxn << 2;
int n, k;
int A[maxn], B[maxn], mina[maxt], minb[maxt], oka[maxt], okb[maxt], lazy[maxt],
    minpre[maxt];
long long ans;
struct node {
  int x, y;
  node operator+(node t) { return A[x] + B[y] < A[t.x] + B[t.y] ? *this : t; }
} ans1[maxt], ans2[maxt], ans3[maxt];
inline int min(int a, int b) { return a < b ? a : b; }
inline void pushup(int now) {
  minpre[now] = min(minpre[(now) << 1], minpre[(now) << 1 | 1]);
  mina[now] = A[mina[(now) << 1]] < A[mina[(now) << 1 | 1]]
                  ? mina[(now) << 1]
                  : mina[(now) << 1 | 1];
  minb[now] = B[minb[(now) << 1]] < B[minb[(now) << 1 | 1]]
                  ? minb[(now) << 1]
                  : minb[(now) << 1 | 1];
  ans1[now] = ans1[(now) << 1] + ans1[(now) << 1 | 1] +
              node{mina[(now) << 1], minb[(now) << 1 | 1]};
  ans2[now] = ans2[(now) << 1] + ans2[(now) << 1 | 1] +
              node{mina[(now) << 1 | 1], minb[(now) << 1]};
  ans3[now] = ans3[(now) << 1] + ans3[(now) << 1 | 1];
  if (minpre[(now) << 1] < minpre[(now) << 1 | 1]) {
    ans3[now] = ans3[now] + ans2[(now) << 1 | 1] +
                node{mina[(now) << 1 | 1], okb[(now) << 1]};
    oka[now] = oka[(now) << 1],
    okb[now] = B[okb[(now) << 1]] < B[minb[(now) << 1 | 1]]
                   ? okb[(now) << 1]
                   : minb[(now) << 1 | 1];
  }
  if (minpre[(now) << 1] == minpre[(now) << 1 | 1]) {
    ans3[now] = ans3[now] + node{oka[(now) << 1 | 1], okb[(now) << 1]};
    oka[now] = oka[(now) << 1], okb[now] = okb[(now) << 1 | 1];
  }
  if (minpre[(now) << 1] > minpre[(now) << 1 | 1]) {
    ans3[now] = ans3[now] + ans2[(now) << 1] +
                node{oka[(now) << 1 | 1], minb[(now) << 1]};
    oka[now] = A[mina[(now) << 1]] < A[oka[(now) << 1 | 1]]
                   ? mina[(now) << 1]
                   : oka[(now) << 1 | 1],
    okb[now] = okb[(now) << 1 | 1];
  }
}
inline void getlazy(int now, int v) { minpre[now] += v, lazy[now] += v; }
inline void pushdown(int now) {
  if (lazy[now])
    getlazy((now) << 1, lazy[now]), getlazy((now) << 1 | 1, lazy[now]),
        lazy[now] = 0;
}
void build(int l, int r, int now) {
  if (l == r) {
    ans1[now] = ans2[now] = node{l, l}, ans3[now] = node{0, 0},
    mina[now] = minb[now] = oka[now] = l, okb[now] = 0;
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, (now) << 1), build(mid + 1, r, (now) << 1 | 1);
  pushup(now);
}
void update(int l, int r, int now, int pos) {
  if (l == r) return;
  int mid = (l + r) >> 1;
  pushdown(now);
  if (pos <= mid)
    update(l, mid, (now) << 1, pos);
  else
    update(mid + 1, r, (now) << 1 | 1, pos);
  pushup(now);
}
void modify(int l, int r, int now, int L, int R, int v) {
  if (L <= l && r <= R) {
    getlazy(now, v);
    return;
  }
  int mid = (l + r) >> 1;
  pushdown(now);
  if (L <= mid) modify(l, mid, (now) << 1, L, R, v);
  if (mid < R) modify(mid + 1, r, (now) << 1 | 1, L, R, v);
  pushup(now);
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
  for (int i = 1; i <= n; i++) scanf("%d", &B[i]);
  A[0] = B[0] = 1000000000, build(0, n, 1);
  for (int i = 1; i <= k; i++) {
    node res = ans1[1] + ans3[1];
    ans += A[res.x] + B[res.y];
    if (res.x < res.y) modify(0, n, 1, res.x, res.y - 1, 1);
    if (res.x > res.y) modify(0, n, 1, res.y, res.x - 1, -1);
    A[res.x] = B[res.y] = 1000000000, update(0, n, 1, res.x),
    update(0, n, 1, res.y);
  }
  printf("%lld\n", ans);
  return 0;
}

### Prompt

Your task is to create a Cpp solution to the following problem:

The plans for HC2 are rather far-fetched: we are just over 500 000 days away from HC2 3387, for example, and accordingly we are planning to have a couple hundred thousand problems in that edition (we hope that programming contests will become wildly more popular). The marmots need to get to work, and they could use a good plan...

Input

Same as the medium version, but the limits have changed: 1 ≤ k ≤ n ≤ 500 000.

Output

Same as the medium version.

Example

Input

8 4
3 8 7 9 9 4 6 8
2 5 9 4 3 8 9 1


Output

32

### Response

```cpp
#include <bits/stdc++.h>
const int maxn = 500005, maxt = maxn << 2;
int n, k;
int A[maxn], B[maxn], mina[maxt], minb[maxt], oka[maxt], okb[maxt], lazy[maxt],
    minpre[maxt];
long long ans;
struct node {
  int x, y;
  node operator+(node t) { return A[x] + B[y] < A[t.x] + B[t.y] ? *this : t; }
} ans1[maxt], ans2[maxt], ans3[maxt];
inline int min(int a, int b) { return a < b ? a : b; }
inline void pushup(int now) {
  minpre[now] = min(minpre[(now) << 1], minpre[(now) << 1 | 1]);
  mina[now] = A[mina[(now) << 1]] < A[mina[(now) << 1 | 1]]
                  ? mina[(now) << 1]
                  : mina[(now) << 1 | 1];
  minb[now] = B[minb[(now) << 1]] < B[minb[(now) << 1 | 1]]
                  ? minb[(now) << 1]
                  : minb[(now) << 1 | 1];
  ans1[now] = ans1[(now) << 1] + ans1[(now) << 1 | 1] +
              node{mina[(now) << 1], minb[(now) << 1 | 1]};
  ans2[now] = ans2[(now) << 1] + ans2[(now) << 1 | 1] +
              node{mina[(now) << 1 | 1], minb[(now) << 1]};
  ans3[now] = ans3[(now) << 1] + ans3[(now) << 1 | 1];
  if (minpre[(now) << 1] < minpre[(now) << 1 | 1]) {
    ans3[now] = ans3[now] + ans2[(now) << 1 | 1] +
                node{mina[(now) << 1 | 1], okb[(now) << 1]};
    oka[now] = oka[(now) << 1],
    okb[now] = B[okb[(now) << 1]] < B[minb[(now) << 1 | 1]]
                   ? okb[(now) << 1]
                   : minb[(now) << 1 | 1];
  }
  if (minpre[(now) << 1] == minpre[(now) << 1 | 1]) {
    ans3[now] = ans3[now] + node{oka[(now) << 1 | 1], okb[(now) << 1]};
    oka[now] = oka[(now) << 1], okb[now] = okb[(now) << 1 | 1];
  }
  if (minpre[(now) << 1] > minpre[(now) << 1 | 1]) {
    ans3[now] = ans3[now] + ans2[(now) << 1] +
                node{oka[(now) << 1 | 1], minb[(now) << 1]};
    oka[now] = A[mina[(now) << 1]] < A[oka[(now) << 1 | 1]]
                   ? mina[(now) << 1]
                   : oka[(now) << 1 | 1],
    okb[now] = okb[(now) << 1 | 1];
  }
}
inline void getlazy(int now, int v) { minpre[now] += v, lazy[now] += v; }
inline void pushdown(int now) {
  if (lazy[now])
    getlazy((now) << 1, lazy[now]), getlazy((now) << 1 | 1, lazy[now]),
        lazy[now] = 0;
}
void build(int l, int r, int now) {
  if (l == r) {
    ans1[now] = ans2[now] = node{l, l}, ans3[now] = node{0, 0},
    mina[now] = minb[now] = oka[now] = l, okb[now] = 0;
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, (now) << 1), build(mid + 1, r, (now) << 1 | 1);
  pushup(now);
}
void update(int l, int r, int now, int pos) {
  if (l == r) return;
  int mid = (l + r) >> 1;
  pushdown(now);
  if (pos <= mid)
    update(l, mid, (now) << 1, pos);
  else
    update(mid + 1, r, (now) << 1 | 1, pos);
  pushup(now);
}
void modify(int l, int r, int now, int L, int R, int v) {
  if (L <= l && r <= R) {
    getlazy(now, v);
    return;
  }
  int mid = (l + r) >> 1;
  pushdown(now);
  if (L <= mid) modify(l, mid, (now) << 1, L, R, v);
  if (mid < R) modify(mid + 1, r, (now) << 1 | 1, L, R, v);
  pushup(now);
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
  for (int i = 1; i <= n; i++) scanf("%d", &B[i]);
  A[0] = B[0] = 1000000000, build(0, n, 1);
  for (int i = 1; i <= k; i++) {
    node res = ans1[1] + ans3[1];
    ans += A[res.x] + B[res.y];
    if (res.x < res.y) modify(0, n, 1, res.x, res.y - 1, 1);
    if (res.x > res.y) modify(0, n, 1, res.y, res.x - 1, -1);
    A[res.x] = B[res.y] = 1000000000, update(0, n, 1, res.x),
    update(0, n, 1, res.y);
  }
  printf("%lld\n", ans);
  return 0;
}

```