#include <bits/stdc++.h>
using namespace std;
const long long N = 3e6 + 10;
const double Pi = acos(-1);
inline long long read() {
  long long x = 0, f = 1, ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
  return x * f;
}
long long n, k, tmp;
long long a[N], b[N];
struct Node {
  long long v, id;
};
priority_queue<Node> pq;
bool operator<(Node a, Node b) { return a.v < b.v; }
void File() { return; }
long long ck(long long x) {
  long long res = 0;
  tmp = 0;
  while (pq.size()) pq.pop();
  for (register long long i = 1; i <= n; ++i) {
    pq.push((Node){-(a[i] - x), 1});
    Node y = pq.top();
    if (-y.v + b[i] < 0) {
      tmp += -y.v + b[i];
      res += y.id;
      pq.pop();
      pq.push((Node){b[i], 0});
    }
  }
  return res;
}
signed main() {
  File();
  n = read(), k = read();
  for (register long long i = 1; i <= n; ++i) a[i] = read();
  for (register long long i = 1; i <= n; ++i) b[i] = read();
  long long l = 0, r = 1e10;
  while (l < r) {
    long long mid = (l + r) >> 1;
    long long ans = ck(mid);
    if (ans < k)
      l = mid + 1;
    else if (ans > k)
      r = mid - 1;
    else
      l = r = mid;
  }
  long long ans = ck(l);
  if (ans != k) tmp += (k - ans) * l;
  tmp += k * l;
  printf("%lld\n", tmp);
  return 0;
}

### Prompt

In Cpp, your task is to solve 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 N = 3e6 + 10;
const double Pi = acos(-1);
inline long long read() {
  long long x = 0, f = 1, ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
  return x * f;
}
long long n, k, tmp;
long long a[N], b[N];
struct Node {
  long long v, id;
};
priority_queue<Node> pq;
bool operator<(Node a, Node b) { return a.v < b.v; }
void File() { return; }
long long ck(long long x) {
  long long res = 0;
  tmp = 0;
  while (pq.size()) pq.pop();
  for (register long long i = 1; i <= n; ++i) {
    pq.push((Node){-(a[i] - x), 1});
    Node y = pq.top();
    if (-y.v + b[i] < 0) {
      tmp += -y.v + b[i];
      res += y.id;
      pq.pop();
      pq.push((Node){b[i], 0});
    }
  }
  return res;
}
signed main() {
  File();
  n = read(), k = read();
  for (register long long i = 1; i <= n; ++i) a[i] = read();
  for (register long long i = 1; i <= n; ++i) b[i] = read();
  long long l = 0, r = 1e10;
  while (l < r) {
    long long mid = (l + r) >> 1;
    long long ans = ck(mid);
    if (ans < k)
      l = mid + 1;
    else if (ans > k)
      r = mid - 1;
    else
      l = r = mid;
  }
  long long ans = ck(l);
  if (ans != k) tmp += (k - ans) * l;
  tmp += k * l;
  printf("%lld\n", tmp);
  return 0;
}

```