#include <bits/stdc++.h>
using namespace std;
string itos(int x) {
  stringstream ss;
  ss << x;
  return ss.str();
}
int a[500010], b[500010], a_[500010], b_[500010];
int n, k;
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> k;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < n; i++) cin >> b[i];
  {
    int l = -2e9, r = 0;
    while (l + 1 < r) {
      int mid = (l + r) / 2;
      for (int i = 0; i < n; i++) a_[i] = a[i] + mid;
      for (int i = 0; i < n; i++) b_[i] = b[i] + mid;
      priority_queue<int, vector<int>, greater<int> > pq1, pq2;
      pair<int, int> cnt = {0, 0};
      for (int i = 0; i < n; i++) {
        pq1.push(a_[i]);
        int v1 = pq1.top() + b_[i];
        int v2 = (pq2.size() ? pq2.top() + b_[i] : 1);
        if (min(v1, v2) < 0) {
          if (v1 < v2) {
            cnt.first++;
            pq1.pop();
            pq2.push(-b_[i]);
          } else {
            pq2.pop();
            pq2.push(-b_[i]);
          }
        }
      }
      while (pq1.size()) pq1.pop();
      while (pq2.size()) pq2.pop();
      long long sum = 0;
      for (int i = 0; i < n; i++) {
        pq1.push(a_[i]);
        int v1 = pq1.top() + b_[i];
        int v2 = (pq2.size() ? pq2.top() + b_[i] : 1);
        if (min(v1, v2) <= 0) {
          sum += min(v1, v2);
          if (v1 <= v2) {
            cnt.second++;
            pq1.pop();
            pq2.push(-b_[i]);
          } else {
            pq2.pop();
            pq2.push(-b_[i]);
          }
        }
      }
      if (cnt.first <= k && cnt.second >= k) {
        cout << sum - 2LL * mid * k << endl;
        return 0;
      } else if (cnt.first > k)
        l = mid + 1;
      else if (cnt.first <= k)
        r = mid;
    }
  }
  cout << "NO WAY" << endl;
  return 0;
}

### Prompt

In CPP, your task is to solve 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;
string itos(int x) {
  stringstream ss;
  ss << x;
  return ss.str();
}
int a[500010], b[500010], a_[500010], b_[500010];
int n, k;
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> k;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < n; i++) cin >> b[i];
  {
    int l = -2e9, r = 0;
    while (l + 1 < r) {
      int mid = (l + r) / 2;
      for (int i = 0; i < n; i++) a_[i] = a[i] + mid;
      for (int i = 0; i < n; i++) b_[i] = b[i] + mid;
      priority_queue<int, vector<int>, greater<int> > pq1, pq2;
      pair<int, int> cnt = {0, 0};
      for (int i = 0; i < n; i++) {
        pq1.push(a_[i]);
        int v1 = pq1.top() + b_[i];
        int v2 = (pq2.size() ? pq2.top() + b_[i] : 1);
        if (min(v1, v2) < 0) {
          if (v1 < v2) {
            cnt.first++;
            pq1.pop();
            pq2.push(-b_[i]);
          } else {
            pq2.pop();
            pq2.push(-b_[i]);
          }
        }
      }
      while (pq1.size()) pq1.pop();
      while (pq2.size()) pq2.pop();
      long long sum = 0;
      for (int i = 0; i < n; i++) {
        pq1.push(a_[i]);
        int v1 = pq1.top() + b_[i];
        int v2 = (pq2.size() ? pq2.top() + b_[i] : 1);
        if (min(v1, v2) <= 0) {
          sum += min(v1, v2);
          if (v1 <= v2) {
            cnt.second++;
            pq1.pop();
            pq2.push(-b_[i]);
          } else {
            pq2.pop();
            pq2.push(-b_[i]);
          }
        }
      }
      if (cnt.first <= k && cnt.second >= k) {
        cout << sum - 2LL * mid * k << endl;
        return 0;
      } else if (cnt.first > k)
        l = mid + 1;
      else if (cnt.first <= k)
        r = mid;
    }
  }
  cout << "NO WAY" << endl;
  return 0;
}

```