#include <bits/stdc++.h>
int main() {
  std::ios_base::sync_with_stdio(0);
  std::cin.tie(0);
  std::cout.tie(0);
  unsigned n, k;
  std::cin >> n >> k;
  const unsigned maxn = 500000;
  std::array<unsigned, maxn> a, b;
  for (unsigned i = 0; i < n; i++) std::cin >> a[i];
  for (unsigned i = 0; i < n; i++) std::cin >> b[i];
  unsigned l = 0, r = 0x3f3f3f3f << 1;
  unsigned long long ans = 0;
  while (l <= r) {
    unsigned mid = (l + r) >> 1, cnt = 0;
    unsigned long long chk = 0;
    std::priority_queue<unsigned, std::vector<unsigned>,
                        std::greater<unsigned> >
        qa;
    std::priority_queue<unsigned> qb;
    for (unsigned i = 0; i < n; i++) {
      qa.push(a[i]);
      int choicea = (int)(qa.top() + b[i] - mid);
      int choiceb = qb.empty() ? INT_MAX : (int)(b[i] - qb.top());
      if (choicea <= choiceb && choicea <= 0) {
        chk += (unsigned long long)choicea;
        ++cnt;
        qa.pop();
        qb.push(b[i]);
      } else if (choiceb < choicea && choiceb < 0) {
        chk += (unsigned long long)choiceb;
        qb.pop();
        qb.push(b[i]);
      }
    }
    if (cnt < k)
      l = mid + 1;
    else {
      r = mid - 1;
      ans = chk + mid * 1ull * k;
    }
  }
  std::cout << ans << std::endl;
  return 0;
}

### Prompt

Create a solution in cpp for 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>
int main() {
  std::ios_base::sync_with_stdio(0);
  std::cin.tie(0);
  std::cout.tie(0);
  unsigned n, k;
  std::cin >> n >> k;
  const unsigned maxn = 500000;
  std::array<unsigned, maxn> a, b;
  for (unsigned i = 0; i < n; i++) std::cin >> a[i];
  for (unsigned i = 0; i < n; i++) std::cin >> b[i];
  unsigned l = 0, r = 0x3f3f3f3f << 1;
  unsigned long long ans = 0;
  while (l <= r) {
    unsigned mid = (l + r) >> 1, cnt = 0;
    unsigned long long chk = 0;
    std::priority_queue<unsigned, std::vector<unsigned>,
                        std::greater<unsigned> >
        qa;
    std::priority_queue<unsigned> qb;
    for (unsigned i = 0; i < n; i++) {
      qa.push(a[i]);
      int choicea = (int)(qa.top() + b[i] - mid);
      int choiceb = qb.empty() ? INT_MAX : (int)(b[i] - qb.top());
      if (choicea <= choiceb && choicea <= 0) {
        chk += (unsigned long long)choicea;
        ++cnt;
        qa.pop();
        qb.push(b[i]);
      } else if (choiceb < choicea && choiceb < 0) {
        chk += (unsigned long long)choiceb;
        qb.pop();
        qb.push(b[i]);
      }
    }
    if (cnt < k)
      l = mid + 1;
    else {
      r = mid - 1;
      ans = chk + mid * 1ull * k;
    }
  }
  std::cout << ans << std::endl;
  return 0;
}

```