#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
int n, k;
long long a[MAXN], b[MAXN];
inline int read() {
  int a = 0, c;
  do c = getchar();
  while (!isdigit(c));
  while (isdigit(c)) a = a * 10 + c - '0', c = getchar();
  return a;
}
priority_queue<long long, vector<long long>, greater<long long> > que;
priority_queue<long long> qa;
int judge(int mid, long long &ans) {
  while (!que.empty()) que.pop();
  while (!qa.empty()) qa.pop();
  int cnt = 0;
  for (register int i = 1; i <= n; i++) {
    que.push(b[i] - mid);
    int a1 = que.top() + a[i], a2 = qa.empty() ? 0 : a[i] - qa.top();
    if (a1 <= a2 && a1 < 0) {
      qa.push(a[i]);
      ans += a1 + mid;
      que.pop();
      cnt++;
    } else if (a2 < 0) {
      ans += a2;
      qa.pop(), qa.push(a[i]);
    }
  }
  return cnt;
}
int main() {
  n = read(), k = read();
  for (register int i = 1; i <= n; i++) b[i] = read();
  for (register int i = 1; i <= n; i++) a[i] = read();
  long long L = -1e12, R = 1e12, mid = 0;
  long long ans;
  while (L <= R) {
    mid = (L + R) >> 1;
    if (judge(mid, ans) < k)
      L = mid + 1;
    else
      R = mid - 1;
  }
  ans = 0;
  judge(L, ans);
  cout << ans << endl;
  return 0;
}

### Prompt

Please formulate 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;
const int MAXN = 500005;
int n, k;
long long a[MAXN], b[MAXN];
inline int read() {
  int a = 0, c;
  do c = getchar();
  while (!isdigit(c));
  while (isdigit(c)) a = a * 10 + c - '0', c = getchar();
  return a;
}
priority_queue<long long, vector<long long>, greater<long long> > que;
priority_queue<long long> qa;
int judge(int mid, long long &ans) {
  while (!que.empty()) que.pop();
  while (!qa.empty()) qa.pop();
  int cnt = 0;
  for (register int i = 1; i <= n; i++) {
    que.push(b[i] - mid);
    int a1 = que.top() + a[i], a2 = qa.empty() ? 0 : a[i] - qa.top();
    if (a1 <= a2 && a1 < 0) {
      qa.push(a[i]);
      ans += a1 + mid;
      que.pop();
      cnt++;
    } else if (a2 < 0) {
      ans += a2;
      qa.pop(), qa.push(a[i]);
    }
  }
  return cnt;
}
int main() {
  n = read(), k = read();
  for (register int i = 1; i <= n; i++) b[i] = read();
  for (register int i = 1; i <= n; i++) a[i] = read();
  long long L = -1e12, R = 1e12, mid = 0;
  long long ans;
  while (L <= R) {
    mid = (L + R) >> 1;
    if (judge(mid, ans) < k)
      L = mid + 1;
    else
      R = mid - 1;
  }
  ans = 0;
  judge(L, ans);
  cout << ans << endl;
  return 0;
}

```