#include <bits/stdc++.h>
using namespace std;
const int N = 5e5;
int n, k, a[N], b[N], num;
long long check(long long mid) {
  long long ret = 0;
  num = 0;
  priority_queue<int> A, B;
  for (int i = 0; i < n; i++) {
    A.push(-a[i]);
    long long newcost = -A.top() + b[i] - mid;
    long long orcost = B.empty() ? 0 : b[i] - B.top();
    if (newcost < orcost) {
      if (newcost < 0) A.pop(), num++, ret += newcost, B.push(b[i]);
    } else if (orcost < 0)
      B.pop(), B.push(b[i]), ret += orcost;
  }
  return ret + mid * 1LL * k;
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; i++) scanf("%d", a + i);
  for (int i = 0; i < n; i++) scanf("%d", b + i);
  long long l = 0, r = 2e9, mid, ans;
  while (l <= r) {
    mid = (l + r) / 2;
    check(mid);
    if (num <= k)
      l = mid + 1, ans = mid;
    else
      r = mid - 1;
  }
  printf("%lld\n", check(ans));
}

### 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 N = 5e5;
int n, k, a[N], b[N], num;
long long check(long long mid) {
  long long ret = 0;
  num = 0;
  priority_queue<int> A, B;
  for (int i = 0; i < n; i++) {
    A.push(-a[i]);
    long long newcost = -A.top() + b[i] - mid;
    long long orcost = B.empty() ? 0 : b[i] - B.top();
    if (newcost < orcost) {
      if (newcost < 0) A.pop(), num++, ret += newcost, B.push(b[i]);
    } else if (orcost < 0)
      B.pop(), B.push(b[i]), ret += orcost;
  }
  return ret + mid * 1LL * k;
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; i++) scanf("%d", a + i);
  for (int i = 0; i < n; i++) scanf("%d", b + i);
  long long l = 0, r = 2e9, mid, ans;
  while (l <= r) {
    mid = (l + r) / 2;
    check(mid);
    if (num <= k)
      l = mid + 1, ans = mid;
    else
      r = mid - 1;
  }
  printf("%lld\n", check(ans));
}

```