#include <bits/stdc++.h>
#pragma warning(disable : 4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;
int IT_MAX = 1 << 19;
const long long MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const long long LL_INF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
const double ERR = 1E-11;
pair<long long, long long> operator+(pair<long long, long long> a,
                                     pair<long long, long long> b) {
  return pair<long long, long long>(a.first + b.first, a.second + b.second);
}
long long A[500050], ta[500050], tb[500050];
long long B[500050];
int main() {
  int N, K, i, j;
  scanf("%d %d", &N, &K);
  for (i = 1; i <= N; i++) scanf("%lld", &A[i]);
  for (i = 1; i <= N; i++) scanf("%lld", &B[i]);
  long long st = -10ll * INF, en = 10ll * INF, mi;
  while (st <= en) {
    mi = (st + en) / 2;
    for (int i = 1; i <= N; i++) ta[i] = A[i] + mi;
    for (int i = 1; i <= N; i++) tb[i] = B[i] + mi;
    priority_queue<long long, vector<long long>, greater<long long> > pq;
    priority_queue<long long> pq2;
    long long sum = 0;
    int cnt[2] = {0, 0};
    for (int i = 1; i <= N; i++) {
      pq.push(ta[i]);
      long long t1 = pq.top();
      long long t2 = pq2.empty() ? -1e18 : pq2.top();
      long long v1 = t1 + tb[i];
      long long v2 = tb[i] - t2;
      if (min(v1, v2) < 0) sum += min(v1, v2);
      if (min(v1, v2) < 0 && v1 < v2) {
        cnt[0]++;
        pq2.push(tb[i]);
        pq.pop();
      }
      if (min(v1, v2) < 0 && v1 >= v2) {
        pq2.pop();
        pq2.push(tb[i]);
      }
    }
    while (!pq.empty()) pq.pop();
    while (!pq2.empty()) pq2.pop();
    long long sum2 = 0;
    for (int i = 1; i <= N; i++) {
      pq.push(ta[i]);
      long long t1 = pq.top();
      long long t2 = pq2.empty() ? -1e18 : pq2.top();
      long long v1 = t1 + tb[i];
      long long v2 = tb[i] - t2;
      if (min(v1, v2) <= 0) sum2 += min(v1, v2);
      if (min(v1, v2) <= 0 && v1 <= v2) {
        cnt[1]++;
        pq2.push(tb[i]);
        pq.pop();
      }
      if (min(v1, v2) <= 0 && v1 > v2) {
        pq2.pop();
        pq2.push(tb[i]);
      }
    }
    if (cnt[0] <= K && cnt[1] >= K) {
      printf("%lld\n", sum - 2LL * K * mi);
      return 0;
    } else {
      if (cnt[0] > K) {
        st = mi + 1;
      } else
        en = mi - 1;
    }
  }
  return !printf("ERR\n");
}

### 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>
#pragma warning(disable : 4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;
int IT_MAX = 1 << 19;
const long long MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const long long LL_INF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
const double ERR = 1E-11;
pair<long long, long long> operator+(pair<long long, long long> a,
                                     pair<long long, long long> b) {
  return pair<long long, long long>(a.first + b.first, a.second + b.second);
}
long long A[500050], ta[500050], tb[500050];
long long B[500050];
int main() {
  int N, K, i, j;
  scanf("%d %d", &N, &K);
  for (i = 1; i <= N; i++) scanf("%lld", &A[i]);
  for (i = 1; i <= N; i++) scanf("%lld", &B[i]);
  long long st = -10ll * INF, en = 10ll * INF, mi;
  while (st <= en) {
    mi = (st + en) / 2;
    for (int i = 1; i <= N; i++) ta[i] = A[i] + mi;
    for (int i = 1; i <= N; i++) tb[i] = B[i] + mi;
    priority_queue<long long, vector<long long>, greater<long long> > pq;
    priority_queue<long long> pq2;
    long long sum = 0;
    int cnt[2] = {0, 0};
    for (int i = 1; i <= N; i++) {
      pq.push(ta[i]);
      long long t1 = pq.top();
      long long t2 = pq2.empty() ? -1e18 : pq2.top();
      long long v1 = t1 + tb[i];
      long long v2 = tb[i] - t2;
      if (min(v1, v2) < 0) sum += min(v1, v2);
      if (min(v1, v2) < 0 && v1 < v2) {
        cnt[0]++;
        pq2.push(tb[i]);
        pq.pop();
      }
      if (min(v1, v2) < 0 && v1 >= v2) {
        pq2.pop();
        pq2.push(tb[i]);
      }
    }
    while (!pq.empty()) pq.pop();
    while (!pq2.empty()) pq2.pop();
    long long sum2 = 0;
    for (int i = 1; i <= N; i++) {
      pq.push(ta[i]);
      long long t1 = pq.top();
      long long t2 = pq2.empty() ? -1e18 : pq2.top();
      long long v1 = t1 + tb[i];
      long long v2 = tb[i] - t2;
      if (min(v1, v2) <= 0) sum2 += min(v1, v2);
      if (min(v1, v2) <= 0 && v1 <= v2) {
        cnt[1]++;
        pq2.push(tb[i]);
        pq.pop();
      }
      if (min(v1, v2) <= 0 && v1 > v2) {
        pq2.pop();
        pq2.push(tb[i]);
      }
    }
    if (cnt[0] <= K && cnt[1] >= K) {
      printf("%lld\n", sum - 2LL * K * mi);
      return 0;
    } else {
      if (cnt[0] > K) {
        st = mi + 1;
      } else
        en = mi - 1;
    }
  }
  return !printf("ERR\n");
}

```