#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
long long a[MAXN], b[MAXN];
int n, k;
pair<long long, int> solve(long long x) {
  priority_queue<long long, vector<long long>, greater<long long> > pq1;
  priority_queue<long long> pq2;
  long long ans = 0;
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    pq1.push(a[i] - x);
    long long cost1 = (pq2.empty() ? 1e18 : (b[i] - pq2.top()));
    long long cost2 = (pq1.empty() ? 1e18 : (pq1.top() + b[i]));
    if (cost1 >= 0 && cost2 >= 0) {
      continue;
    }
    if (cost1 <= cost2) {
      pq2.pop();
      pq2.push(b[i]);
      ans += cost1;
    } else {
      pq1.pop();
      pq2.push(b[i]);
      ans += cost2;
      cnt++;
    }
  }
  return make_pair(ans, cnt);
}
int main() {
  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
  }
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &b[i]);
  }
  long long s = 0, e = 2e9;
  while (s != e) {
    long long m = (s + e + 1) / 2;
    if (solve(m).second > k)
      e = m - 1;
    else
      s = m;
  }
  cout << solve(s).first + s * k;
}

### Prompt

Your task is to create 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;
long long a[MAXN], b[MAXN];
int n, k;
pair<long long, int> solve(long long x) {
  priority_queue<long long, vector<long long>, greater<long long> > pq1;
  priority_queue<long long> pq2;
  long long ans = 0;
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    pq1.push(a[i] - x);
    long long cost1 = (pq2.empty() ? 1e18 : (b[i] - pq2.top()));
    long long cost2 = (pq1.empty() ? 1e18 : (pq1.top() + b[i]));
    if (cost1 >= 0 && cost2 >= 0) {
      continue;
    }
    if (cost1 <= cost2) {
      pq2.pop();
      pq2.push(b[i]);
      ans += cost1;
    } else {
      pq1.pop();
      pq2.push(b[i]);
      ans += cost2;
      cnt++;
    }
  }
  return make_pair(ans, cnt);
}
int main() {
  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
  }
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &b[i]);
  }
  long long s = 0, e = 2e9;
  while (s != e) {
    long long m = (s + e + 1) / 2;
    if (solve(m).second > k)
      e = m - 1;
    else
      s = m;
  }
  cout << solve(s).first + s * k;
}

```