#include <bits/stdc++.h>
using namespace std;
const int maxn = 500010;
template <typename Tp>
inline int getmin(Tp &x, Tp y) {
  return y < x ? x = y, 1 : 0;
}
template <typename Tp>
inline int getmax(Tp &x, Tp y) {
  return y > x ? x = y, 1 : 0;
}
template <typename Tp>
inline void read(Tp &x) {
  x = 0;
  int f = 0;
  char ch = getchar();
  while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
  if (ch == '-') f = 1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  if (f) x = -x;
}
int n, k, m, L, R = 2e9, cnt, a[maxn], b[maxn];
long long ans = 1e18, sum;
struct Heap {
  int p, a[maxn];
  void push(int x) {
    a[++p] = x;
    push_heap(a + 1, a + p + 1);
  }
  void pop() {
    pop_heap(a + 1, a + p + 1);
    --p;
  }
} H;
struct GHeap {
  int p, a[maxn];
  void push(int x) {
    a[++p] = x;
    push_heap(a + 1, a + p + 1, greater<int>());
  }
  void pop() {
    pop_heap(a + 1, a + p + 1, greater<int>());
    --p;
  }
} GH;
void check(int m) {
  int x1, x2;
  H.p = GH.p = 0;
  cnt = 0;
  sum = 0ll;
  for (int i = 1; i <= n; i++) {
    x2 = 2e9;
    GH.push(a[i]);
    x1 = b[i] - m + GH.a[1];
    if (H.p > 0) x2 = b[i] - H.a[1];
    if (x1 >= 0 && x2 >= 0) continue;
    if (x1 <= x2) {
      ++cnt;
      sum += x1;
      GH.pop();
      H.push(b[i]);
    }
    if (x1 > x2) {
      sum += x2;
      H.pop();
      H.push(b[i]);
    }
  }
}
int main() {
  read(n);
  read(k);
  for (int i = 1; i <= n; i++) read(a[i]);
  for (int i = 1; i <= n; i++) read(b[i]);
  while (L <= R) {
    m = ((long long)L + R) >> 1;
    check(m);
    if (cnt >= k) {
      ans = sum + (long long)k * m;
      R = m - 1;
    } else
      L = m + 1;
  }
  printf("%lld\n", ans);
  return 0;
}

### Prompt

Your task is to create 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 int maxn = 500010;
template <typename Tp>
inline int getmin(Tp &x, Tp y) {
  return y < x ? x = y, 1 : 0;
}
template <typename Tp>
inline int getmax(Tp &x, Tp y) {
  return y > x ? x = y, 1 : 0;
}
template <typename Tp>
inline void read(Tp &x) {
  x = 0;
  int f = 0;
  char ch = getchar();
  while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
  if (ch == '-') f = 1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  if (f) x = -x;
}
int n, k, m, L, R = 2e9, cnt, a[maxn], b[maxn];
long long ans = 1e18, sum;
struct Heap {
  int p, a[maxn];
  void push(int x) {
    a[++p] = x;
    push_heap(a + 1, a + p + 1);
  }
  void pop() {
    pop_heap(a + 1, a + p + 1);
    --p;
  }
} H;
struct GHeap {
  int p, a[maxn];
  void push(int x) {
    a[++p] = x;
    push_heap(a + 1, a + p + 1, greater<int>());
  }
  void pop() {
    pop_heap(a + 1, a + p + 1, greater<int>());
    --p;
  }
} GH;
void check(int m) {
  int x1, x2;
  H.p = GH.p = 0;
  cnt = 0;
  sum = 0ll;
  for (int i = 1; i <= n; i++) {
    x2 = 2e9;
    GH.push(a[i]);
    x1 = b[i] - m + GH.a[1];
    if (H.p > 0) x2 = b[i] - H.a[1];
    if (x1 >= 0 && x2 >= 0) continue;
    if (x1 <= x2) {
      ++cnt;
      sum += x1;
      GH.pop();
      H.push(b[i]);
    }
    if (x1 > x2) {
      sum += x2;
      H.pop();
      H.push(b[i]);
    }
  }
}
int main() {
  read(n);
  read(k);
  for (int i = 1; i <= n; i++) read(a[i]);
  for (int i = 1; i <= n; i++) read(b[i]);
  while (L <= R) {
    m = ((long long)L + R) >> 1;
    check(m);
    if (cnt >= k) {
      ans = sum + (long long)k * m;
      R = m - 1;
    } else
      L = m + 1;
  }
  printf("%lld\n", ans);
  return 0;
}

```