#include <bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7, INF = 0x3f3f3f3f;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long qpow(long long a, long long n) {
  long long r = 1 % P;
  for (a %= P; n; a = a * a % P, n >>= 1)
    if (n & 1) r = r * a % P;
  return r;
}
long long inv(long long first) {
  return first <= 1 ? 1 : inv(P % first) * (P - P / first) % P;
}
inline int rd() {
  int first = 0;
  char p = getchar();
  while (p < '0' || p > '9') p = getchar();
  while (p >= '0' && p <= '9') first = first * 10 + p - '0', p = getchar();
  return first;
}
const int N = 1e6 + 50;
long long n, k, a[N], b[N];
priority_queue<long long, vector<long long>, greater<long long> > q[2];
signed main() {
  scanf("%lld%lld", &n, &k);
  for (long long i = 1; i <= n; ++i) scanf("%lld", a + i);
  for (long long i = 1; i <= n; ++i) scanf("%lld", b + i);
  long long l = 0, r = 1e15;
  long long ans = 0;
  while (l <= r) {
    for (long long i = 0; i <= 1; ++i)
      while (q[i].size()) q[i].pop();
    long long ret = 0;
    long long cnt = 0;
    for (long long i = 1; i <= n; ++i) {
      q[0].push(a[i]);
      long long t1 = q[0].top() + b[i] - ((l + r) >> 1);
      long long t2 = q[1].empty() ? INF : b[i] + q[1].top();
      if (t1 < 0 && t1 < t2) {
        ret += t1, ++cnt;
        q[1].push(-b[i]);
        q[0].pop();
      } else if (t2 < 0) {
        ret += t2;
        q[1].pop();
        q[1].push(-b[i]);
      }
    }
    if (cnt >= k)
      ans = ret + (long long)k * ((l + r) >> 1), r = ((l + r) >> 1) - 1;
    else
      l = ((l + r) >> 1) + 1;
  }
  printf("%lld\n", ans);
}

### Prompt

Please create a solution in CPP 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 P = 1e9 + 7, INF = 0x3f3f3f3f;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long qpow(long long a, long long n) {
  long long r = 1 % P;
  for (a %= P; n; a = a * a % P, n >>= 1)
    if (n & 1) r = r * a % P;
  return r;
}
long long inv(long long first) {
  return first <= 1 ? 1 : inv(P % first) * (P - P / first) % P;
}
inline int rd() {
  int first = 0;
  char p = getchar();
  while (p < '0' || p > '9') p = getchar();
  while (p >= '0' && p <= '9') first = first * 10 + p - '0', p = getchar();
  return first;
}
const int N = 1e6 + 50;
long long n, k, a[N], b[N];
priority_queue<long long, vector<long long>, greater<long long> > q[2];
signed main() {
  scanf("%lld%lld", &n, &k);
  for (long long i = 1; i <= n; ++i) scanf("%lld", a + i);
  for (long long i = 1; i <= n; ++i) scanf("%lld", b + i);
  long long l = 0, r = 1e15;
  long long ans = 0;
  while (l <= r) {
    for (long long i = 0; i <= 1; ++i)
      while (q[i].size()) q[i].pop();
    long long ret = 0;
    long long cnt = 0;
    for (long long i = 1; i <= n; ++i) {
      q[0].push(a[i]);
      long long t1 = q[0].top() + b[i] - ((l + r) >> 1);
      long long t2 = q[1].empty() ? INF : b[i] + q[1].top();
      if (t1 < 0 && t1 < t2) {
        ret += t1, ++cnt;
        q[1].push(-b[i]);
        q[0].pop();
      } else if (t2 < 0) {
        ret += t2;
        q[1].pop();
        q[1].push(-b[i]);
      }
    }
    if (cnt >= k)
      ans = ret + (long long)k * ((l + r) >> 1), r = ((l + r) >> 1) - 1;
    else
      l = ((l + r) >> 1) + 1;
  }
  printf("%lld\n", ans);
}

```