#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500100;
int n, k;
long long a[MAXN], b[MAXN];
pair<long long, int> check(long long c) {
  priority_queue<long long> q1, q2;
  long long ret1 = 0;
  int ret2 = 0;
  for (int i = (0); i < int(n); i++) {
    q1.push(-a[i]);
    int how = 0;
    if (-q1.top() + b[i] - c < 0) how++;
    if (!q2.empty() && q2.top() > b[i]) how++;
    if (!how) continue;
    if (q2.empty() || -q1.top() + b[i] - c < -q2.top() + b[i]) {
      ret2++;
      ret1 += -q1.top() + b[i] - c;
      q1.pop();
      q2.push(b[i]);
    } else {
      ret1 += -q2.top() + b[i];
      q2.pop();
      q2.push(b[i]);
    }
  }
  return make_pair(ret1, ret2);
}
int main() {
  scanf("%d %d", &n, &k);
  for (int i = (0); i < int(n); i++) scanf("%lld", &a[i]);
  for (int i = (0); i < int(n); i++) scanf("%lld", &b[i]);
  long long lo = -(1LL << 50), hi = (1LL << 50), mid;
  while (lo != hi) {
    mid = (lo + hi) / 2;
    pair<long long, int> t = check(mid);
    if (t.second == k) {
      lo = mid;
      break;
    }
    if (t.second > k)
      hi = mid;
    else
      lo = mid + 1;
  }
  printf("%lld\n", check(lo).first + k * lo);
  return 0;
}

### Prompt

Generate 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 = 500100;
int n, k;
long long a[MAXN], b[MAXN];
pair<long long, int> check(long long c) {
  priority_queue<long long> q1, q2;
  long long ret1 = 0;
  int ret2 = 0;
  for (int i = (0); i < int(n); i++) {
    q1.push(-a[i]);
    int how = 0;
    if (-q1.top() + b[i] - c < 0) how++;
    if (!q2.empty() && q2.top() > b[i]) how++;
    if (!how) continue;
    if (q2.empty() || -q1.top() + b[i] - c < -q2.top() + b[i]) {
      ret2++;
      ret1 += -q1.top() + b[i] - c;
      q1.pop();
      q2.push(b[i]);
    } else {
      ret1 += -q2.top() + b[i];
      q2.pop();
      q2.push(b[i]);
    }
  }
  return make_pair(ret1, ret2);
}
int main() {
  scanf("%d %d", &n, &k);
  for (int i = (0); i < int(n); i++) scanf("%lld", &a[i]);
  for (int i = (0); i < int(n); i++) scanf("%lld", &b[i]);
  long long lo = -(1LL << 50), hi = (1LL << 50), mid;
  while (lo != hi) {
    mid = (lo + hi) / 2;
    pair<long long, int> t = check(mid);
    if (t.second == k) {
      lo = mid;
      break;
    }
    if (t.second > k)
      hi = mid;
    else
      lo = mid + 1;
  }
  printf("%lld\n", check(lo).first + k * lo);
  return 0;
}

```