#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 5;
const long long inf = 2e9;
char buf[1 << 12], *pp1 = buf, *pp2 = buf, nc;
int ny;
inline char gc() {
  return pp1 == pp2 &&
                 (pp2 = (pp1 = buf) + fread(buf, 1, 1 << 12, stdin), pp1 == pp2)
             ? EOF
             : *pp1++;
}
inline int read() {
  int x = 0;
  for (ny = 1; nc = gc(), (nc < 48 || nc > 57) && nc != EOF;)
    if (nc == 45) ny = -1;
  if (nc < 0) return nc;
  for (x = nc - 48; nc = gc(), 47 < nc && nc < 58 && nc != EOF;
       x = (x << 3) + (x << 1) + (nc ^ 48))
    ;
  return x * ny;
}
int n, K, a[MAXN], b[MAXN];
long long Ans;
inline int check(long long k) {
  priority_queue<pair<long long, int>, vector<pair<long long, int> >,
                 greater<pair<long long, int> > >
      q;
  int cnt = 0;
  Ans = 0;
  for (int i = (1); i <= (n); i++) {
    if (a[i] + k < 0) q.push(make_pair(a[i], 1));
    if (!q.empty()) {
      pair<long long, int> t = q.top();
      int w = t.second;
      long long val = t.first;
      if (b[i] + val + k < 0)
        Ans += b[i] + val + k, cnt += w, q.pop(),
            q.push(make_pair(-k - b[i], 0));
    }
    if (cnt > K) return K + 1;
  }
  return cnt;
}
inline void Solve() {
  long long l = -inf, r = 0, ans = 0;
  while (l <= r) {
    long long mid = l + r >> 1;
    if (check(mid) <= K)
      ans = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  check(ans), cout << Ans - 1ll * ans * K << "\n";
}
int main() {
  n = read(), K = read();
  for (int i = (1); i <= (n); i++) a[i] = read();
  for (int i = (1); i <= (n); i++) b[i] = read();
  Solve();
  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;
const int MAXN = 5e5 + 5;
const long long inf = 2e9;
char buf[1 << 12], *pp1 = buf, *pp2 = buf, nc;
int ny;
inline char gc() {
  return pp1 == pp2 &&
                 (pp2 = (pp1 = buf) + fread(buf, 1, 1 << 12, stdin), pp1 == pp2)
             ? EOF
             : *pp1++;
}
inline int read() {
  int x = 0;
  for (ny = 1; nc = gc(), (nc < 48 || nc > 57) && nc != EOF;)
    if (nc == 45) ny = -1;
  if (nc < 0) return nc;
  for (x = nc - 48; nc = gc(), 47 < nc && nc < 58 && nc != EOF;
       x = (x << 3) + (x << 1) + (nc ^ 48))
    ;
  return x * ny;
}
int n, K, a[MAXN], b[MAXN];
long long Ans;
inline int check(long long k) {
  priority_queue<pair<long long, int>, vector<pair<long long, int> >,
                 greater<pair<long long, int> > >
      q;
  int cnt = 0;
  Ans = 0;
  for (int i = (1); i <= (n); i++) {
    if (a[i] + k < 0) q.push(make_pair(a[i], 1));
    if (!q.empty()) {
      pair<long long, int> t = q.top();
      int w = t.second;
      long long val = t.first;
      if (b[i] + val + k < 0)
        Ans += b[i] + val + k, cnt += w, q.pop(),
            q.push(make_pair(-k - b[i], 0));
    }
    if (cnt > K) return K + 1;
  }
  return cnt;
}
inline void Solve() {
  long long l = -inf, r = 0, ans = 0;
  while (l <= r) {
    long long mid = l + r >> 1;
    if (check(mid) <= K)
      ans = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  check(ans), cout << Ans - 1ll * ans * K << "\n";
}
int main() {
  n = read(), K = read();
  for (int i = (1); i <= (n); i++) a[i] = read();
  for (int i = (1); i <= (n); i++) b[i] = read();
  Solve();
  return 0;
}

```