#include <bits/stdc++.h>
using namespace std;
long long n, m, a[500001], b[500001], ans, sum, cnt;
inline bool check(long long x) {
  sum = cnt = 0;
  priority_queue<pair<long long, long long>,
                 vector<pair<long long, long long> >,
                 greater<pair<long long, long long> > >
      q;
  for (register long long i = 1; i <= n; ++i) {
    q.push(make_pair(a[i], 0));
    if (q.top().first + b[i] + x <= 0) {
      sum += q.top().first + b[i] + x;
      cnt += q.top().second ^ 1;
      q.pop();
      q.push(make_pair(-b[i] - x, 1));
    }
  }
  if (cnt >= m) ans = sum;
  return cnt >= m;
}
signed main() {
  scanf("%lld%lld", &n, &m);
  for (register long long i = 1; i <= n; ++i) scanf("%lld", &a[i]);
  for (register long long i = 1; i <= n; ++i) scanf("%lld", &b[i]);
  long long l = -1e18, r = 1e18, mid;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (check(mid)) {
      ans = sum - m * mid;
      l = mid + 1;
    } else
      r = mid - 1;
  }
  printf("%lld\n", ans);
  return 0;
}

### 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;
long long n, m, a[500001], b[500001], ans, sum, cnt;
inline bool check(long long x) {
  sum = cnt = 0;
  priority_queue<pair<long long, long long>,
                 vector<pair<long long, long long> >,
                 greater<pair<long long, long long> > >
      q;
  for (register long long i = 1; i <= n; ++i) {
    q.push(make_pair(a[i], 0));
    if (q.top().first + b[i] + x <= 0) {
      sum += q.top().first + b[i] + x;
      cnt += q.top().second ^ 1;
      q.pop();
      q.push(make_pair(-b[i] - x, 1));
    }
  }
  if (cnt >= m) ans = sum;
  return cnt >= m;
}
signed main() {
  scanf("%lld%lld", &n, &m);
  for (register long long i = 1; i <= n; ++i) scanf("%lld", &a[i]);
  for (register long long i = 1; i <= n; ++i) scanf("%lld", &b[i]);
  long long l = -1e18, r = 1e18, mid;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (check(mid)) {
      ans = sum - m * mid;
      l = mid + 1;
    } else
      r = mid - 1;
  }
  printf("%lld\n", ans);
  return 0;
}

```