#include <bits/stdc++.h>
using namespace std;
int IN() {
  int c, f, x;
  while (!isdigit(c = getchar()) && c != '-')
    ;
  c == '-' ? (f = 1, x = 0) : (f = 0, x = c - '0');
  while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + c - '0';
  return !f ? x : -x;
}
const int N = 500000 + 19;
struct node {
  long long val;
  int isA;
  bool operator<(const node &B) const {
    return val > B.val || val == B.val && isA < B.isA;
  }
};
priority_queue<node> Q;
int A[N], B[N];
int n, K, cnt, l, r;
long long res, sum;
void calc(int delta) {
  sum = 0, cnt = 0;
  while (!Q.empty()) Q.pop();
  for (int i = 1; i < n + 1; i++) {
    Q.push((node){A[i], 1});
    node T = Q.top();
    if (B[i] - delta + T.val <= 0) {
      cnt += T.isA;
      sum += B[i] - delta + T.val;
      Q.pop();
      Q.push((node){-(B[i] - delta), 0});
    }
  }
}
int main() {
  n = IN(), K = IN();
  for (int i = 1; i < n + 1; i++) A[i] = IN();
  for (int i = 1; i < n + 1; i++) B[i] = IN();
  l = 0, r = int(2e9);
  while (l <= r) {
    int mid = (0ll + l + r) / 2;
    calc(mid);
    if (cnt == K) res = sum + 1ll * cnt * mid;
    if (cnt <= K) {
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  cout << res << endl;
}

### 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;
int IN() {
  int c, f, x;
  while (!isdigit(c = getchar()) && c != '-')
    ;
  c == '-' ? (f = 1, x = 0) : (f = 0, x = c - '0');
  while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + c - '0';
  return !f ? x : -x;
}
const int N = 500000 + 19;
struct node {
  long long val;
  int isA;
  bool operator<(const node &B) const {
    return val > B.val || val == B.val && isA < B.isA;
  }
};
priority_queue<node> Q;
int A[N], B[N];
int n, K, cnt, l, r;
long long res, sum;
void calc(int delta) {
  sum = 0, cnt = 0;
  while (!Q.empty()) Q.pop();
  for (int i = 1; i < n + 1; i++) {
    Q.push((node){A[i], 1});
    node T = Q.top();
    if (B[i] - delta + T.val <= 0) {
      cnt += T.isA;
      sum += B[i] - delta + T.val;
      Q.pop();
      Q.push((node){-(B[i] - delta), 0});
    }
  }
}
int main() {
  n = IN(), K = IN();
  for (int i = 1; i < n + 1; i++) A[i] = IN();
  for (int i = 1; i < n + 1; i++) B[i] = IN();
  l = 0, r = int(2e9);
  while (l <= r) {
    int mid = (0ll + l + r) / 2;
    calc(mid);
    if (cnt == K) res = sum + 1ll * cnt * mid;
    if (cnt <= K) {
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  cout << res << endl;
}

```