#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void read(T &x) {
  long long f = 0;
  x = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  if (f) x = -x;
}
const long long N = 500005;
long long a[N], b[N], x[N], y[N], n, k, cnt;
long long ans;
void calc(long long mid) {
  for (long long i = (1); i <= (n); i++) {
    x[i] = a[i] - mid;
    y[i] = b[i];
  }
  priority_queue<pair<long long, long long>,
                 vector<pair<long long, long long> >,
                 greater<pair<long long, long long> > >
      Q;
  cnt = 0, ans = 0;
  for (long long i = (1); i <= (n); i++) {
    Q.push(make_pair(x[i], 1));
    if (Q.top().first + y[i] < 0) {
      ans += Q.top().first + y[i], cnt += Q.top().second;
      Q.pop(), Q.push(make_pair(-y[i], 0));
    }
  }
}
signed main() {
  read(n), read(k);
  for (long long i = (1); i <= (n); i++) read(a[i]);
  for (long long i = (1); i <= (n); i++) read(b[i]);
  long long l = 0, r = 2e9, mid;
  while (l < r) {
    mid = (l + r + 1) >> 1;
    calc(mid);
    if (cnt <= k)
      l = mid;
    else
      r = mid - 1;
  }
  calc(l);
  cout << ans + (long long)l * cnt << endl;
  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;
template <class T>
inline void read(T &x) {
  long long f = 0;
  x = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  if (f) x = -x;
}
const long long N = 500005;
long long a[N], b[N], x[N], y[N], n, k, cnt;
long long ans;
void calc(long long mid) {
  for (long long i = (1); i <= (n); i++) {
    x[i] = a[i] - mid;
    y[i] = b[i];
  }
  priority_queue<pair<long long, long long>,
                 vector<pair<long long, long long> >,
                 greater<pair<long long, long long> > >
      Q;
  cnt = 0, ans = 0;
  for (long long i = (1); i <= (n); i++) {
    Q.push(make_pair(x[i], 1));
    if (Q.top().first + y[i] < 0) {
      ans += Q.top().first + y[i], cnt += Q.top().second;
      Q.pop(), Q.push(make_pair(-y[i], 0));
    }
  }
}
signed main() {
  read(n), read(k);
  for (long long i = (1); i <= (n); i++) read(a[i]);
  for (long long i = (1); i <= (n); i++) read(b[i]);
  long long l = 0, r = 2e9, mid;
  while (l < r) {
    mid = (l + r + 1) >> 1;
    calc(mid);
    if (cnt <= k)
      l = mid;
    else
      r = mid - 1;
  }
  calc(l);
  cout << ans + (long long)l * cnt << endl;
  return 0;
}

```