#include <bits/stdc++.h>
using namespace std;
priority_queue<long long, vector<long long>, greater<long long> > Qa;
priority_queue<long long> Qb;
int n, k;
long long val, st, en, mid, a[500010], b[500010];
int test(long long c) {
  val = 0;
  long long mn = 0, mnn[6], id = 0;
  int sz = 0, szz[6];
  while (!Qa.empty()) Qa.pop();
  while (!Qb.empty()) Qb.pop();
  for (int i = 1; i <= n; i++) {
    mn = 0;
    mnn[0] = val;
    szz[0] = sz;
    mnn[1] = val + a[i] + b[i] - c;
    szz[1] = sz + 1;
    szz[2] = sz;
    if (Qb.empty())
      mnn[2] = val;
    else
      mnn[2] = val + b[i] - Qb.top();
    if (!Qa.empty()) {
      mnn[3] = val + Qa.top() + b[i] - c;
      szz[3] = sz + 1;
    } else {
      mnn[3] = val;
      szz[3] = sz;
    }
    for (int i = 0; i < 4; i++) mn = min(mn, mnn[i]);
    for (int i = 0; i < 4; i++)
      if (mn == mnn[i]) sz = max(sz, szz[i]);
    for (int i = 0; i < 4; i++)
      if (mn == mnn[i] && sz == szz[i]) id = i;
    if (id == 1)
      Qb.push(b[i]);
    else {
      if (id == 2) {
        if (!Qb.empty()) {
          Qb.pop();
          Qb.push(b[i]);
        }
      }
      if (id == 3) {
        if (!Qa.empty()) {
          Qa.pop();
          Qb.push(b[i]);
        }
      }
      Qa.push(a[i]);
    }
    val = mn;
  }
  return sz;
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%I64d", &a[i]);
  for (int i = 1; i <= n; i++) scanf("%I64d", &b[i]);
  st = 0;
  en = 2000000100;
  while (en - st > 1) {
    mid = st + en >> 1;
    int tt = test(mid);
    if (k < tt) en = mid;
    if (k == tt) {
      printf("%I64d", val + mid * k);
      return 0;
    }
    if (k > tt) st = mid;
  }
  test(en);
  printf("%I64d", val + en * k);
}

### 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;
priority_queue<long long, vector<long long>, greater<long long> > Qa;
priority_queue<long long> Qb;
int n, k;
long long val, st, en, mid, a[500010], b[500010];
int test(long long c) {
  val = 0;
  long long mn = 0, mnn[6], id = 0;
  int sz = 0, szz[6];
  while (!Qa.empty()) Qa.pop();
  while (!Qb.empty()) Qb.pop();
  for (int i = 1; i <= n; i++) {
    mn = 0;
    mnn[0] = val;
    szz[0] = sz;
    mnn[1] = val + a[i] + b[i] - c;
    szz[1] = sz + 1;
    szz[2] = sz;
    if (Qb.empty())
      mnn[2] = val;
    else
      mnn[2] = val + b[i] - Qb.top();
    if (!Qa.empty()) {
      mnn[3] = val + Qa.top() + b[i] - c;
      szz[3] = sz + 1;
    } else {
      mnn[3] = val;
      szz[3] = sz;
    }
    for (int i = 0; i < 4; i++) mn = min(mn, mnn[i]);
    for (int i = 0; i < 4; i++)
      if (mn == mnn[i]) sz = max(sz, szz[i]);
    for (int i = 0; i < 4; i++)
      if (mn == mnn[i] && sz == szz[i]) id = i;
    if (id == 1)
      Qb.push(b[i]);
    else {
      if (id == 2) {
        if (!Qb.empty()) {
          Qb.pop();
          Qb.push(b[i]);
        }
      }
      if (id == 3) {
        if (!Qa.empty()) {
          Qa.pop();
          Qb.push(b[i]);
        }
      }
      Qa.push(a[i]);
    }
    val = mn;
  }
  return sz;
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%I64d", &a[i]);
  for (int i = 1; i <= n; i++) scanf("%I64d", &b[i]);
  st = 0;
  en = 2000000100;
  while (en - st > 1) {
    mid = st + en >> 1;
    int tt = test(mid);
    if (k < tt) en = mid;
    if (k == tt) {
      printf("%I64d", val + mid * k);
      return 0;
    }
    if (k > tt) st = mid;
  }
  test(en);
  printf("%I64d", val + en * k);
}

```