#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
const long long INF = 0x3f3f3f3f3f3f3f3f;
template <typename T>
inline void read(T &AKNOI) {
  T x = 0, flag = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') flag = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  AKNOI = flag * x;
}
int n, k, a[MAXN], b[MAXN];
priority_queue<int, vector<int>, greater<int> > qa;
priority_queue<int> qb;
void init() {
  read(n);
  read(k);
  for (int i = 1; i <= n; ++i) {
    read(a[i]);
  }
  for (int i = 1; i <= n; ++i) {
    read(b[i]);
  }
}
void solve() {
  long long L = 0, R = INF, ans = 0;
  while (L <= R) {
    long long M = (L + R) >> 1, cur = 0;
    int cnt = 0;
    while (!qa.empty()) qa.pop();
    while (!qb.empty()) qb.pop();
    for (int i = 1; i <= n; ++i) {
      qa.push(a[i]);
      long long v1 = qa.top() + b[i] - M;
      long long v2 = INF;
      if (!qb.empty()) v2 = b[i] - qb.top();
      if (v1 > 0 && v2 > 0) continue;
      if (v1 <= v2) {
        cur += v1;
        qa.pop();
        qb.push(b[i]);
        ++cnt;
      } else {
        cur += v2;
        qb.pop();
        qb.push(b[i]);
      }
    }
    if (cnt >= k) {
      ans = cur + M * k;
      R = M - 1;
    } else {
      L = M + 1;
    }
  }
  printf("%lld\n", ans);
}
int main() {
  init();
  solve();
  return 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;
const int MAXN = 500005;
const long long INF = 0x3f3f3f3f3f3f3f3f;
template <typename T>
inline void read(T &AKNOI) {
  T x = 0, flag = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') flag = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  AKNOI = flag * x;
}
int n, k, a[MAXN], b[MAXN];
priority_queue<int, vector<int>, greater<int> > qa;
priority_queue<int> qb;
void init() {
  read(n);
  read(k);
  for (int i = 1; i <= n; ++i) {
    read(a[i]);
  }
  for (int i = 1; i <= n; ++i) {
    read(b[i]);
  }
}
void solve() {
  long long L = 0, R = INF, ans = 0;
  while (L <= R) {
    long long M = (L + R) >> 1, cur = 0;
    int cnt = 0;
    while (!qa.empty()) qa.pop();
    while (!qb.empty()) qb.pop();
    for (int i = 1; i <= n; ++i) {
      qa.push(a[i]);
      long long v1 = qa.top() + b[i] - M;
      long long v2 = INF;
      if (!qb.empty()) v2 = b[i] - qb.top();
      if (v1 > 0 && v2 > 0) continue;
      if (v1 <= v2) {
        cur += v1;
        qa.pop();
        qb.push(b[i]);
        ++cnt;
      } else {
        cur += v2;
        qb.pop();
        qb.push(b[i]);
      }
    }
    if (cnt >= k) {
      ans = cur + M * k;
      R = M - 1;
    } else {
      L = M + 1;
    }
  }
  printf("%lld\n", ans);
}
int main() {
  init();
  solve();
  return 0;
}

```