#include <bits/stdc++.h>
using namespace std;
struct dp {
  int64_t n;
  vector<int64_t> as;
  vector<int64_t> bs;
  pair<int64_t, int64_t> run(int64_t l) {
    int64_t used = 0;
    int64_t res = 0;
    priority_queue<pair<int64_t, int64_t>> pq;
    for (int64_t i = 0; i < n; i++) {
      pq.push(make_pair(-bs[i] + l, 1ll));
      auto fr = pq.top();
      if (-fr.first + as[i] <= 0) {
        pq.pop();
        used += fr.second;
        res += -fr.first + as[i];
        pq.push(make_pair(as[i], 0ll));
      }
    }
    return make_pair(res, used);
  }
  int64_t calc(int64_t k) {
    reverse(as.begin(), as.end());
    reverse(bs.begin(), bs.end());
    int64_t l = -1e13;
    int64_t r = 1e13;
    while (l + 1 < r) {
      int64_t m = (l + r) / 2;
      if (run(m).second > k)
        r = m;
      else
        l = m;
    }
    auto rnl = run(l);
    auto rnr = run(r);
    int64_t kl = rnl.second;
    int64_t kr = rnr.second;
    int64_t rsl = rnl.first + kl * l;
    int64_t rsr = rnr.first + kr * r;
    if (kl == k) return rsl;
    if (kr == k) return rsr;
    int64_t dk = kr - kl;
    int64_t dr = rsr - rsl;
    int64_t df = dr / dk;
    return rsl + (k - kl) * df;
  }
};
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int64_t n, k;
  cin >> n >> k;
  dp d;
  d.as.resize(n);
  d.bs.resize(n);
  d.n = n;
  for (int64_t i = 0; i < n; i++) cin >> d.as[i];
  for (int64_t i = 0; i < n; i++) cin >> d.bs[i];
  cout << d.calc(k) << "\n";
}

### 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;
struct dp {
  int64_t n;
  vector<int64_t> as;
  vector<int64_t> bs;
  pair<int64_t, int64_t> run(int64_t l) {
    int64_t used = 0;
    int64_t res = 0;
    priority_queue<pair<int64_t, int64_t>> pq;
    for (int64_t i = 0; i < n; i++) {
      pq.push(make_pair(-bs[i] + l, 1ll));
      auto fr = pq.top();
      if (-fr.first + as[i] <= 0) {
        pq.pop();
        used += fr.second;
        res += -fr.first + as[i];
        pq.push(make_pair(as[i], 0ll));
      }
    }
    return make_pair(res, used);
  }
  int64_t calc(int64_t k) {
    reverse(as.begin(), as.end());
    reverse(bs.begin(), bs.end());
    int64_t l = -1e13;
    int64_t r = 1e13;
    while (l + 1 < r) {
      int64_t m = (l + r) / 2;
      if (run(m).second > k)
        r = m;
      else
        l = m;
    }
    auto rnl = run(l);
    auto rnr = run(r);
    int64_t kl = rnl.second;
    int64_t kr = rnr.second;
    int64_t rsl = rnl.first + kl * l;
    int64_t rsr = rnr.first + kr * r;
    if (kl == k) return rsl;
    if (kr == k) return rsr;
    int64_t dk = kr - kl;
    int64_t dr = rsr - rsl;
    int64_t df = dr / dk;
    return rsl + (k - kl) * df;
  }
};
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int64_t n, k;
  cin >> n >> k;
  dp d;
  d.as.resize(n);
  d.bs.resize(n);
  d.n = n;
  for (int64_t i = 0; i < n; i++) cin >> d.as[i];
  for (int64_t i = 0; i < n; i++) cin >> d.bs[i];
  cout << d.calc(k) << "\n";
}

```