#include <bits/stdc++.h>
using namespace std;
struct Q {
  pair<int, int> mnA, mnB;
  int mn;
  pair<int, pair<int, int> > opt1, opt2;
  pair<int, int> ml, mr;
  Q(int A = 1000000005, int B = 1000000005) {
    mn = 0, mnA = pair<int, int>(A, -1), mnB = pair<int, int>(B, -1),
    opt1 = opt2 = pair<int, pair<int, int> >(
        1000000005 * 2, pair<int, int>(1000000005, 1000000005)),
    ml = mr = pair<int, int>(1000000005, -1);
  }
};
Q merge(Q l, Q r) {
  Q ret;
  ret.mn = min(l.mn, r.mn);
  ret.mnA = min(l.mnA, r.mnA);
  ret.mnB = min(l.mnB, r.mnB);
  ret.opt2 = pair<int, pair<int, int> >(
      ret.mnA.first + ret.mnB.first,
      pair<int, int>(ret.mnA.second, ret.mnB.second));
  if (ret.mn == l.mn)
    ret.ml = l.ml;
  else
    ret.ml = min(l.mnA, r.ml);
  if (ret.mn == r.mn)
    ret.mr = r.mr;
  else
    ret.mr = min(l.mr, r.mnB);
  ret.opt1 = min(
      pair<int, pair<int, int> >(l.mnA.first + r.mnB.first,
                                 pair<int, int>(l.mnA.second, r.mnB.second)),
      min(l.opt1, r.opt1));
  ret.opt1 = min(ret.opt1, pair<int, pair<int, int> >(
                               l.mr.first + r.ml.first,
                               pair<int, int>(r.ml.second, l.mr.second)));
  if (l.mn > ret.mn) {
    ret.opt1 = min(ret.opt1, pair<int, pair<int, int> >(
                                 l.mnB.first + r.ml.first,
                                 pair<int, int>(r.ml.second, l.mnB.second)));
    ret.opt1 = min(ret.opt1, l.opt2);
  }
  if (r.mn > ret.mn) {
    ret.opt1 = min(ret.opt1, pair<int, pair<int, int> >(
                                 l.mr.first + r.mnA.first,
                                 pair<int, int>(r.mnA.second, l.mr.second)));
    ret.opt1 = min(ret.opt1, r.opt2);
  }
  return ret;
}
struct segtree {
  Q seg[512 * 1024 * 2];
  int add[512 * 1024 * 2];
  int mum;
  void init(int n) {
    mum = 1;
    while (mum < n) mum <<= 1;
    for (int i = 0; i < mum * 2; i++) seg[i] = Q(), add[i] = 0;
  }
  void ins(int k, int A, int B) {
    k += mum - 1;
    seg[k].mnA = pair<int, int>(A, k - mum + 1);
    seg[k].mnB = seg[k].mr = pair<int, int>(B, k - mum + 1);
    seg[k].opt1 = seg[k].opt2 = pair<int, pair<int, int> >(
        A + B, pair<int, int>(k - mum + 1, k - mum + 1));
    while (k > 0) {
      k = (k - 1) / 2;
      seg[k] = merge(seg[k * 2 + 1], seg[k * 2 + 2]);
      seg[k].mn += add[k];
    }
  }
  void update(int a, int b, int k, int l, int r, int v) {
    if (b <= l || r <= a) return;
    if (a <= l && r <= b) {
      add[k] += v;
      seg[k].mn += v;
    } else {
      update(a, b, k * 2 + 1, l, (l + r) / 2, v);
      update(a, b, k * 2 + 2, (l + r) / 2, r, v);
      seg[k] = merge(seg[k * 2 + 1], seg[k * 2 + 2]);
      seg[k].mn += add[k];
    }
  }
  void update(int a, int b, int v) { update(a, b, 0, 0, mum, v); }
  void see() {
    for (int i = 0; i < mum * 2; i++) {
      if (i == 2 || i == 5 || i == 6 || i >= 11) continue;
      printf("%d %d %d : %d %d %d\n", i, seg[i].mn, add[i], seg[i].opt1.first,
             seg[i].opt1.second.first, seg[i].opt1.second.second);
      printf("* %d %d : %d %d\n", seg[i].ml.first, seg[i].ml.second,
             seg[i].mr.first, seg[i].mr.second);
    }
  }
  pair<int, int> get() { return seg[0].opt1.second; }
};
segtree seg;
int A[500005], B[500005];
int main() {
  int n, k;
  scanf("%d %d", &n, &k);
  for (int i = 0; i < n; i++) scanf("%d", &A[i]);
  for (int i = 0; i < n; i++) scanf("%d", &B[i]);
  seg.init(n + 2);
  for (int i = 0; i < n; i++) {
    seg.ins(i, A[i], B[i]);
  }
  long long int ret = 0;
  for (int i = 0; i < k; i++) {
    pair<int, int> p = seg.get();
    int a = p.first, b = p.second;
    ret += A[a] + B[b];
    A[a] = 1000000005, B[b] = 1000000005;
    seg.ins(a, A[a], B[a]);
    seg.ins(b, A[b], B[b]);
    seg.update(0, a + 1, -1);
    seg.update(0, b + 1, 1);
  }
  printf("%lld\n", ret);
  return 0;
}

### Prompt

Your challenge is to write 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>
using namespace std;
struct Q {
  pair<int, int> mnA, mnB;
  int mn;
  pair<int, pair<int, int> > opt1, opt2;
  pair<int, int> ml, mr;
  Q(int A = 1000000005, int B = 1000000005) {
    mn = 0, mnA = pair<int, int>(A, -1), mnB = pair<int, int>(B, -1),
    opt1 = opt2 = pair<int, pair<int, int> >(
        1000000005 * 2, pair<int, int>(1000000005, 1000000005)),
    ml = mr = pair<int, int>(1000000005, -1);
  }
};
Q merge(Q l, Q r) {
  Q ret;
  ret.mn = min(l.mn, r.mn);
  ret.mnA = min(l.mnA, r.mnA);
  ret.mnB = min(l.mnB, r.mnB);
  ret.opt2 = pair<int, pair<int, int> >(
      ret.mnA.first + ret.mnB.first,
      pair<int, int>(ret.mnA.second, ret.mnB.second));
  if (ret.mn == l.mn)
    ret.ml = l.ml;
  else
    ret.ml = min(l.mnA, r.ml);
  if (ret.mn == r.mn)
    ret.mr = r.mr;
  else
    ret.mr = min(l.mr, r.mnB);
  ret.opt1 = min(
      pair<int, pair<int, int> >(l.mnA.first + r.mnB.first,
                                 pair<int, int>(l.mnA.second, r.mnB.second)),
      min(l.opt1, r.opt1));
  ret.opt1 = min(ret.opt1, pair<int, pair<int, int> >(
                               l.mr.first + r.ml.first,
                               pair<int, int>(r.ml.second, l.mr.second)));
  if (l.mn > ret.mn) {
    ret.opt1 = min(ret.opt1, pair<int, pair<int, int> >(
                                 l.mnB.first + r.ml.first,
                                 pair<int, int>(r.ml.second, l.mnB.second)));
    ret.opt1 = min(ret.opt1, l.opt2);
  }
  if (r.mn > ret.mn) {
    ret.opt1 = min(ret.opt1, pair<int, pair<int, int> >(
                                 l.mr.first + r.mnA.first,
                                 pair<int, int>(r.mnA.second, l.mr.second)));
    ret.opt1 = min(ret.opt1, r.opt2);
  }
  return ret;
}
struct segtree {
  Q seg[512 * 1024 * 2];
  int add[512 * 1024 * 2];
  int mum;
  void init(int n) {
    mum = 1;
    while (mum < n) mum <<= 1;
    for (int i = 0; i < mum * 2; i++) seg[i] = Q(), add[i] = 0;
  }
  void ins(int k, int A, int B) {
    k += mum - 1;
    seg[k].mnA = pair<int, int>(A, k - mum + 1);
    seg[k].mnB = seg[k].mr = pair<int, int>(B, k - mum + 1);
    seg[k].opt1 = seg[k].opt2 = pair<int, pair<int, int> >(
        A + B, pair<int, int>(k - mum + 1, k - mum + 1));
    while (k > 0) {
      k = (k - 1) / 2;
      seg[k] = merge(seg[k * 2 + 1], seg[k * 2 + 2]);
      seg[k].mn += add[k];
    }
  }
  void update(int a, int b, int k, int l, int r, int v) {
    if (b <= l || r <= a) return;
    if (a <= l && r <= b) {
      add[k] += v;
      seg[k].mn += v;
    } else {
      update(a, b, k * 2 + 1, l, (l + r) / 2, v);
      update(a, b, k * 2 + 2, (l + r) / 2, r, v);
      seg[k] = merge(seg[k * 2 + 1], seg[k * 2 + 2]);
      seg[k].mn += add[k];
    }
  }
  void update(int a, int b, int v) { update(a, b, 0, 0, mum, v); }
  void see() {
    for (int i = 0; i < mum * 2; i++) {
      if (i == 2 || i == 5 || i == 6 || i >= 11) continue;
      printf("%d %d %d : %d %d %d\n", i, seg[i].mn, add[i], seg[i].opt1.first,
             seg[i].opt1.second.first, seg[i].opt1.second.second);
      printf("* %d %d : %d %d\n", seg[i].ml.first, seg[i].ml.second,
             seg[i].mr.first, seg[i].mr.second);
    }
  }
  pair<int, int> get() { return seg[0].opt1.second; }
};
segtree seg;
int A[500005], B[500005];
int main() {
  int n, k;
  scanf("%d %d", &n, &k);
  for (int i = 0; i < n; i++) scanf("%d", &A[i]);
  for (int i = 0; i < n; i++) scanf("%d", &B[i]);
  seg.init(n + 2);
  for (int i = 0; i < n; i++) {
    seg.ins(i, A[i], B[i]);
  }
  long long int ret = 0;
  for (int i = 0; i < k; i++) {
    pair<int, int> p = seg.get();
    int a = p.first, b = p.second;
    ret += A[a] + B[b];
    A[a] = 1000000005, B[b] = 1000000005;
    seg.ins(a, A[a], B[a]);
    seg.ins(b, A[b], B[b]);
    seg.update(0, a + 1, -1);
    seg.update(0, b + 1, 1);
  }
  printf("%lld\n", ret);
  return 0;
}

```