#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, f = 1, c = getchar();
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + (c ^ 48);
    c = getchar();
  }
  return f == 1 ? x : -x;
}
const int N = 5e5 + 4, inf = 0x3f3f3f3f;
int n, k, a[2][N];
long long ans;
struct node {
  int u, v;
  node(int x = 0, int y = 0) : u(x), v(y) {}
  inline bool operator<(const node &x) const {
    return a[0][u] + a[1][v] < a[0][x.u] + a[1][x.v];
  }
};
inline int cmp(int x, int y, int o) { return a[o][x] < a[o][y] ? x : y; }
namespace seg {
node t[N << 2][3];
int c[N << 2][4], val[N << 2], lz[N << 2];
void pushup(int p) {
  val[p] = min(val[(p << 1)], val[(p << 1 | 1)]);
  c[p][0] = cmp(c[(p << 1)][0], c[(p << 1 | 1)][0], 0);
  c[p][1] = cmp(c[(p << 1)][1], c[(p << 1 | 1)][1], 1);
  c[p][2] = cmp(c[(p << 1)][val[p] == val[(p << 1)] ? 2 : 0],
                val[(p << 1)] == val[p]
                    ? 0
                    : c[(p << 1 | 1)][val[p] == val[(p << 1 | 1)] ? 2 : 0],
                0);
  c[p][3] = cmp(val[p] == val[(p << 1 | 1)]
                    ? 0
                    : c[(p << 1)][val[p] == val[(p << 1)] ? 3 : 1],
                c[(p << 1 | 1)][val[p] == val[(p << 1 | 1)] ? 3 : 1], 1);
  t[p][0] = min(min(t[(p << 1)][0], t[(p << 1 | 1)][0]),
                node(c[(p << 1)][0], c[(p << 1 | 1)][1]));
  t[p][1] = min(min(t[(p << 1)][1], t[(p << 1 | 1)][1]),
                node(c[(p << 1 | 1)][0], c[(p << 1)][1]));
  t[p][2] = min(min(t[(p << 1)][val[p] == val[(p << 1)] ? 2 : 1],
                    t[(p << 1 | 1)][val[p] == val[(p << 1 | 1)] ? 2 : 1]),
                node(c[(p << 1 | 1)][val[(p << 1 | 1)] == val[p] ? 2 : 0],
                     c[(p << 1)][val[p] == val[(p << 1)] ? 3 : 1]));
}
void build(int p, int l, int r) {
  if (l == r) {
    t[p][0] = node(r, r);
    t[p][1] = t[p][2] = node(0, 0);
    c[p][0] = c[p][1] = c[p][2] = r;
    c[p][3] = 0;
    return;
  }
  build((p << 1), l, ((l + r) >> 1));
  build((p << 1 | 1), ((l + r) >> 1) + 1, r);
  pushup(p);
}
inline void pushdown(int p) {
  if (!lz[p]) return;
  val[(p << 1)] += lz[p];
  lz[(p << 1)] += lz[p];
  val[(p << 1 | 1)] += lz[p];
  lz[(p << 1 | 1)] += lz[p];
  lz[p] = 0;
}
void change(int p, int l, int r, int x, int o) {
  if (l == r) {
    t[p][0] = node(0, 0);
    c[p][o] = c[p][o + 2] = 0;
    return;
  }
  pushdown(p);
  if (x <= ((l + r) >> 1))
    change((p << 1), l, ((l + r) >> 1), x, o);
  else
    change((p << 1 | 1), ((l + r) >> 1) + 1, r, x, o);
  pushup(p);
}
void modify(int p, int l, int r, int ql, int qr, int v) {
  if (ql <= l && r <= qr) {
    lz[p] += v;
    val[p] += v;
    return;
  }
  pushdown(p);
  if (ql <= ((l + r) >> 1)) modify((p << 1), l, ((l + r) >> 1), ql, qr, v);
  if (((l + r) >> 1) < qr)
    modify((p << 1 | 1), ((l + r) >> 1) + 1, r, ql, qr, v);
  pushup(p);
}
}  // namespace seg
int main() {
  n = read();
  k = read();
  for (int i = 1; i <= n; i++) a[0][i] = read();
  for (int i = 1; i <= n; i++) a[1][i] = read();
  a[0][0] = a[1][0] = inf;
  seg::build(1, 1, n);
  for (int T = 1, u, v; T <= k; T++) {
    static node tmp;
    tmp = min(seg::t[1][0], seg::t[1][seg::val[1] > 0 ? 1 : 2]);
    u = tmp.u;
    v = tmp.v;
    ans += a[0][u] + a[1][v];
    seg::change(1, 1, n, u, 0);
    seg::change(1, 1, n, v, 1);
    if (u < v) seg::modify(1, 1, n, u, v - 1, 1);
    if (v < u) seg::modify(1, 1, n, v, u - 1, -1);
  }
  cout << ans << "\n";
  return (0 - 0);
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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>
using namespace std;
inline int read() {
  int x = 0, f = 1, c = getchar();
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + (c ^ 48);
    c = getchar();
  }
  return f == 1 ? x : -x;
}
const int N = 5e5 + 4, inf = 0x3f3f3f3f;
int n, k, a[2][N];
long long ans;
struct node {
  int u, v;
  node(int x = 0, int y = 0) : u(x), v(y) {}
  inline bool operator<(const node &x) const {
    return a[0][u] + a[1][v] < a[0][x.u] + a[1][x.v];
  }
};
inline int cmp(int x, int y, int o) { return a[o][x] < a[o][y] ? x : y; }
namespace seg {
node t[N << 2][3];
int c[N << 2][4], val[N << 2], lz[N << 2];
void pushup(int p) {
  val[p] = min(val[(p << 1)], val[(p << 1 | 1)]);
  c[p][0] = cmp(c[(p << 1)][0], c[(p << 1 | 1)][0], 0);
  c[p][1] = cmp(c[(p << 1)][1], c[(p << 1 | 1)][1], 1);
  c[p][2] = cmp(c[(p << 1)][val[p] == val[(p << 1)] ? 2 : 0],
                val[(p << 1)] == val[p]
                    ? 0
                    : c[(p << 1 | 1)][val[p] == val[(p << 1 | 1)] ? 2 : 0],
                0);
  c[p][3] = cmp(val[p] == val[(p << 1 | 1)]
                    ? 0
                    : c[(p << 1)][val[p] == val[(p << 1)] ? 3 : 1],
                c[(p << 1 | 1)][val[p] == val[(p << 1 | 1)] ? 3 : 1], 1);
  t[p][0] = min(min(t[(p << 1)][0], t[(p << 1 | 1)][0]),
                node(c[(p << 1)][0], c[(p << 1 | 1)][1]));
  t[p][1] = min(min(t[(p << 1)][1], t[(p << 1 | 1)][1]),
                node(c[(p << 1 | 1)][0], c[(p << 1)][1]));
  t[p][2] = min(min(t[(p << 1)][val[p] == val[(p << 1)] ? 2 : 1],
                    t[(p << 1 | 1)][val[p] == val[(p << 1 | 1)] ? 2 : 1]),
                node(c[(p << 1 | 1)][val[(p << 1 | 1)] == val[p] ? 2 : 0],
                     c[(p << 1)][val[p] == val[(p << 1)] ? 3 : 1]));
}
void build(int p, int l, int r) {
  if (l == r) {
    t[p][0] = node(r, r);
    t[p][1] = t[p][2] = node(0, 0);
    c[p][0] = c[p][1] = c[p][2] = r;
    c[p][3] = 0;
    return;
  }
  build((p << 1), l, ((l + r) >> 1));
  build((p << 1 | 1), ((l + r) >> 1) + 1, r);
  pushup(p);
}
inline void pushdown(int p) {
  if (!lz[p]) return;
  val[(p << 1)] += lz[p];
  lz[(p << 1)] += lz[p];
  val[(p << 1 | 1)] += lz[p];
  lz[(p << 1 | 1)] += lz[p];
  lz[p] = 0;
}
void change(int p, int l, int r, int x, int o) {
  if (l == r) {
    t[p][0] = node(0, 0);
    c[p][o] = c[p][o + 2] = 0;
    return;
  }
  pushdown(p);
  if (x <= ((l + r) >> 1))
    change((p << 1), l, ((l + r) >> 1), x, o);
  else
    change((p << 1 | 1), ((l + r) >> 1) + 1, r, x, o);
  pushup(p);
}
void modify(int p, int l, int r, int ql, int qr, int v) {
  if (ql <= l && r <= qr) {
    lz[p] += v;
    val[p] += v;
    return;
  }
  pushdown(p);
  if (ql <= ((l + r) >> 1)) modify((p << 1), l, ((l + r) >> 1), ql, qr, v);
  if (((l + r) >> 1) < qr)
    modify((p << 1 | 1), ((l + r) >> 1) + 1, r, ql, qr, v);
  pushup(p);
}
}  // namespace seg
int main() {
  n = read();
  k = read();
  for (int i = 1; i <= n; i++) a[0][i] = read();
  for (int i = 1; i <= n; i++) a[1][i] = read();
  a[0][0] = a[1][0] = inf;
  seg::build(1, 1, n);
  for (int T = 1, u, v; T <= k; T++) {
    static node tmp;
    tmp = min(seg::t[1][0], seg::t[1][seg::val[1] > 0 ? 1 : 2]);
    u = tmp.u;
    v = tmp.v;
    ans += a[0][u] + a[1][v];
    seg::change(1, 1, n, u, 0);
    seg::change(1, 1, n, v, 1);
    if (u < v) seg::modify(1, 1, n, u, v - 1, 1);
    if (v < u) seg::modify(1, 1, n, v, u - 1, -1);
  }
  cout << ans << "\n";
  return (0 - 0);
}

```