#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
const long long INF = (long long)1e18;
int N, K;
long long a[MAXN], b[MAXN];
void load() {
  scanf("%d%d", &N, &K);
  for (int i = 0; i < N; i++) scanf("%lld", a + i);
  for (int i = 0; i < N; i++) scanf("%lld", b + i);
}
pair<long long, int> get_opt(long long c) {
  for (int i = 0; i < N; i++) {
    a[i] -= c;
    b[i] -= c;
  }
  multiset<long long> S, B;
  long long res = 0;
  for (int i = 0; i < N; i++) {
    S.insert(a[i]);
    long long p = b[i] + (S.empty() ? INF : *S.begin());
    long long q = b[i] - (B.empty() ? -INF : *B.rbegin());
    if (p < 0 && p < q) {
      S.erase(S.begin());
      B.insert(b[i]);
      res += p;
    } else if (q < 0) {
      B.erase(--B.end());
      B.insert(b[i]);
      res += q;
    }
  }
  for (int i = 0; i < N; i++) {
    a[i] += c;
    b[i] += c;
  }
  return pair<long long, int>(res, B.size());
}
long long solve() {
  long long lo = 0, hi = (long long)1e12;
  while (lo < hi) {
    int mid = (lo + hi) / 2;
    pair<long long, int> tmp = get_opt(mid);
    if (tmp.second >= K)
      hi = mid;
    else
      lo = mid + 1;
  }
  pair<long long, int> sol = get_opt(lo);
  return sol.first + 2 * sol.second * lo;
}
int main() {
  load();
  printf("%lld\n", solve());
  return 0;
}

### Prompt

Please formulate 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 = 500005;
const long long INF = (long long)1e18;
int N, K;
long long a[MAXN], b[MAXN];
void load() {
  scanf("%d%d", &N, &K);
  for (int i = 0; i < N; i++) scanf("%lld", a + i);
  for (int i = 0; i < N; i++) scanf("%lld", b + i);
}
pair<long long, int> get_opt(long long c) {
  for (int i = 0; i < N; i++) {
    a[i] -= c;
    b[i] -= c;
  }
  multiset<long long> S, B;
  long long res = 0;
  for (int i = 0; i < N; i++) {
    S.insert(a[i]);
    long long p = b[i] + (S.empty() ? INF : *S.begin());
    long long q = b[i] - (B.empty() ? -INF : *B.rbegin());
    if (p < 0 && p < q) {
      S.erase(S.begin());
      B.insert(b[i]);
      res += p;
    } else if (q < 0) {
      B.erase(--B.end());
      B.insert(b[i]);
      res += q;
    }
  }
  for (int i = 0; i < N; i++) {
    a[i] += c;
    b[i] += c;
  }
  return pair<long long, int>(res, B.size());
}
long long solve() {
  long long lo = 0, hi = (long long)1e12;
  while (lo < hi) {
    int mid = (lo + hi) / 2;
    pair<long long, int> tmp = get_opt(mid);
    if (tmp.second >= K)
      hi = mid;
    else
      lo = mid + 1;
  }
  pair<long long, int> sol = get_opt(lo);
  return sol.first + 2 * sol.second * lo;
}
int main() {
  load();
  printf("%lld\n", solve());
  return 0;
}

```