#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 5e5 + 5;
long long n, k;
long long a[MAXN], b[MAXN];
inline long long read() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) (ch == '-') && (f = -f), ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  return x * f;
}
struct Node {
  long long val;
  long long cnt;
  Node(long long val = 0, long long cnt = 0) : val(val), cnt(cnt){};
  inline bool operator<(const Node &tmp) const {
    return val != tmp.val ? val > tmp.val : cnt < tmp.cnt;
  }
};
priority_queue<Node> q;
inline Node solve(long long mid) {
  long long i;
  Node ans;
  while (!q.empty()) q.pop();
  for (i = 1; i <= n; ++i) {
    q.push(Node(a[i] - mid, 1));
    Node tmp = q.top();
    if (tmp.val + b[i] <= 0) {
      q.pop();
      ans.val += tmp.val + b[i];
      ans.cnt += tmp.cnt;
      q.push(Node(-b[i], 0));
    }
  }
  return ans;
}
int main() {
  long long i;
  n = read();
  k = read();
  for (i = 1; i <= n; ++i) a[i] = read();
  for (i = 1; i <= n; ++i) b[i] = read();
  long long l = 0, r = 2147483647, mid, delta;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (solve(mid).cnt >= k)
      delta = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  printf("%lld\n", solve(delta).val + delta * k);
  return 0;
}

### Prompt

Generate 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 long long MAXN = 5e5 + 5;
long long n, k;
long long a[MAXN], b[MAXN];
inline long long read() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) (ch == '-') && (f = -f), ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  return x * f;
}
struct Node {
  long long val;
  long long cnt;
  Node(long long val = 0, long long cnt = 0) : val(val), cnt(cnt){};
  inline bool operator<(const Node &tmp) const {
    return val != tmp.val ? val > tmp.val : cnt < tmp.cnt;
  }
};
priority_queue<Node> q;
inline Node solve(long long mid) {
  long long i;
  Node ans;
  while (!q.empty()) q.pop();
  for (i = 1; i <= n; ++i) {
    q.push(Node(a[i] - mid, 1));
    Node tmp = q.top();
    if (tmp.val + b[i] <= 0) {
      q.pop();
      ans.val += tmp.val + b[i];
      ans.cnt += tmp.cnt;
      q.push(Node(-b[i], 0));
    }
  }
  return ans;
}
int main() {
  long long i;
  n = read();
  k = read();
  for (i = 1; i <= n; ++i) a[i] = read();
  for (i = 1; i <= n; ++i) b[i] = read();
  long long l = 0, r = 2147483647, mid, delta;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (solve(mid).cnt >= k)
      delta = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  printf("%lld\n", solve(delta).val + delta * k);
  return 0;
}

```