#include <bits/stdc++.h>
using namespace std;
namespace sky_chen {
long long tetetetetmp;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
inline long long read() {
  long long ans = 0;
  char a =
      p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2)
          ? EOF
          : *p1++;
  while (a > '9' || a < '0')
    a = p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2)
            ? EOF
            : *p1++;
  while (a >= '0' && a <= '9')
    ans = ans * 10 + (a ^ 48),
    a = p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2)
            ? EOF
            : *p1++;
  return ans;
}
inline char red() {
  long long ans = 0;
  char a =
      p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2)
          ? EOF
          : *p1++;
  while (a > 'z' || a < 'a')
    a = p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2)
            ? EOF
            : *p1++;
  return a;
}
inline void print(long long x) {
  if (x > 9) print(x / 10);
  *O++ = x % 10 + '0';
}
inline void cadd(long long &x, long long y) { x = (x + y) % 998244353; }
inline void cmin(long long &x, long long y) { x = min(x, y); }
inline void cmax(long long &x, long long y) { x = max(x, y); }
inline long long max(long long a, long long b) { return a < b ? b : a; }
inline long long min(long long a, long long b) { return a < b ? a : b; }
inline void swap(long long &a, long long &b) {
  tetetetetmp = a;
  a = b;
  b = tetetetetmp;
}
long long qpow(long long n, long long base = 998244353 - 2) {
  long long ans = 1;
  while (base) {
    if (base & 1) ans = ans * n % 998244353;
    n = n * n % 998244353;
    base >>= 1;
  }
  return ans;
}
const int maxn = 3e5 + 5;
long long n, k, a[500005], b[500005];
priority_queue<pair<long long, long long> > q;
int yyds() {
  n = read();
  k = read();
  for (register int i = 1; i <= n; i++) a[i] = read();
  long long l = 0, r = 2e9, mid;
  for (register int i = 1; i <= n; i++) b[i] = read();
  while (l <= r) {
    mid = (l + r) >> 1;
    long long s = 0;
    long long cnt = 0;
    for (int i = 1; i <= n; i++) {
      q.push(make_pair(-a[i], 0));
      long long tmp = b[i] - ((l + r) >> 1) - q.top().first;
      if (tmp < 0) s += tmp, q.pop(), q.push(make_pair(b[i] - mid, 1ll));
    }
    while (!q.empty()) cnt += q.top().second, q.pop();
    if (cnt == k) return !printf("%lld\n", s + k * mid);
    if (cnt < k)
      l = mid + 1;
    else
      r = mid - 1;
  }
  fwrite(obuf, 1, O - obuf, stdout);
  return 0;
}
}  // namespace sky_chen
int main() { return sky_chen::yyds(); }

### Prompt

Construct a CPP code solution to the problem outlined:

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;
namespace sky_chen {
long long tetetetetmp;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
inline long long read() {
  long long ans = 0;
  char a =
      p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2)
          ? EOF
          : *p1++;
  while (a > '9' || a < '0')
    a = p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2)
            ? EOF
            : *p1++;
  while (a >= '0' && a <= '9')
    ans = ans * 10 + (a ^ 48),
    a = p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2)
            ? EOF
            : *p1++;
  return ans;
}
inline char red() {
  long long ans = 0;
  char a =
      p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2)
          ? EOF
          : *p1++;
  while (a > 'z' || a < 'a')
    a = p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2)
            ? EOF
            : *p1++;
  return a;
}
inline void print(long long x) {
  if (x > 9) print(x / 10);
  *O++ = x % 10 + '0';
}
inline void cadd(long long &x, long long y) { x = (x + y) % 998244353; }
inline void cmin(long long &x, long long y) { x = min(x, y); }
inline void cmax(long long &x, long long y) { x = max(x, y); }
inline long long max(long long a, long long b) { return a < b ? b : a; }
inline long long min(long long a, long long b) { return a < b ? a : b; }
inline void swap(long long &a, long long &b) {
  tetetetetmp = a;
  a = b;
  b = tetetetetmp;
}
long long qpow(long long n, long long base = 998244353 - 2) {
  long long ans = 1;
  while (base) {
    if (base & 1) ans = ans * n % 998244353;
    n = n * n % 998244353;
    base >>= 1;
  }
  return ans;
}
const int maxn = 3e5 + 5;
long long n, k, a[500005], b[500005];
priority_queue<pair<long long, long long> > q;
int yyds() {
  n = read();
  k = read();
  for (register int i = 1; i <= n; i++) a[i] = read();
  long long l = 0, r = 2e9, mid;
  for (register int i = 1; i <= n; i++) b[i] = read();
  while (l <= r) {
    mid = (l + r) >> 1;
    long long s = 0;
    long long cnt = 0;
    for (int i = 1; i <= n; i++) {
      q.push(make_pair(-a[i], 0));
      long long tmp = b[i] - ((l + r) >> 1) - q.top().first;
      if (tmp < 0) s += tmp, q.pop(), q.push(make_pair(b[i] - mid, 1ll));
    }
    while (!q.empty()) cnt += q.top().second, q.pop();
    if (cnt == k) return !printf("%lld\n", s + k * mid);
    if (cnt < k)
      l = mid + 1;
    else
      r = mid - 1;
  }
  fwrite(obuf, 1, O - obuf, stdout);
  return 0;
}
}  // namespace sky_chen
int main() { return sky_chen::yyds(); }

```