#include <bits/stdc++.h>
using namespace std;
const int RLEN = 1 << 18 | 1;
inline char nc() {
  static char ibuf[RLEN], *ib, *ob;
  (ib == ob) && (ob = (ib = ibuf) + fread(ibuf, 1, RLEN, stdin));
  return (ib == ob) ? -1 : *ib++;
}
inline int rd() {
  char ch = nc();
  int i = 0, f = 1;
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = nc();
  }
  while (isdigit(ch)) {
    i = (i << 1) + (i << 3) + ch - '0';
    ch = nc();
  }
  return i * f;
}
const int N = 5e5 + 50;
int n, k, a[N], b[N];
inline pair<long long, int> calc(long long val) {
  long long sum = 0, cnt = 0;
  priority_queue<int, vector<int>, greater<int> > aa, bb;
  for (int i = 1; i <= n; i++) {
    aa.push(a[i]);
    long long val1 = sum;
    long long val2 = (aa.size() ? aa.top() + b[i] - val + sum : 1e18);
    long long val3 = (bb.size() ? bb.top() + b[i] + sum : 1e18);
    if (val1 <= val2 && val1 <= val3) continue;
    if (val2 < val3) {
      sum = aa.top() + b[i] - val + sum;
      aa.pop();
      bb.push(-b[i]);
      ++cnt;
    } else {
      sum = bb.top() + b[i] + sum;
      bb.pop();
      bb.push(-b[i]);
    }
  }
  return pair<long long, int>(sum, cnt);
}
int main() {
  n = rd(), k = rd();
  for (int i = 1; i <= n; i++) a[i] = rd();
  for (int i = 1; i <= n; i++) b[i] = rd();
  long long l = 0, r = 1e12, ans = 0;
  while (l <= r) {
    long long mid = (l + r) >> 1;
    pair<long long, int> tp = calc(mid);
    if (tp.second <= k)
      ans = tp.first + (long long)k * mid, l = mid + 1;
    else
      r = mid - 1;
  }
  cout << ans << '\n';
}

### Prompt

Generate 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 RLEN = 1 << 18 | 1;
inline char nc() {
  static char ibuf[RLEN], *ib, *ob;
  (ib == ob) && (ob = (ib = ibuf) + fread(ibuf, 1, RLEN, stdin));
  return (ib == ob) ? -1 : *ib++;
}
inline int rd() {
  char ch = nc();
  int i = 0, f = 1;
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = nc();
  }
  while (isdigit(ch)) {
    i = (i << 1) + (i << 3) + ch - '0';
    ch = nc();
  }
  return i * f;
}
const int N = 5e5 + 50;
int n, k, a[N], b[N];
inline pair<long long, int> calc(long long val) {
  long long sum = 0, cnt = 0;
  priority_queue<int, vector<int>, greater<int> > aa, bb;
  for (int i = 1; i <= n; i++) {
    aa.push(a[i]);
    long long val1 = sum;
    long long val2 = (aa.size() ? aa.top() + b[i] - val + sum : 1e18);
    long long val3 = (bb.size() ? bb.top() + b[i] + sum : 1e18);
    if (val1 <= val2 && val1 <= val3) continue;
    if (val2 < val3) {
      sum = aa.top() + b[i] - val + sum;
      aa.pop();
      bb.push(-b[i]);
      ++cnt;
    } else {
      sum = bb.top() + b[i] + sum;
      bb.pop();
      bb.push(-b[i]);
    }
  }
  return pair<long long, int>(sum, cnt);
}
int main() {
  n = rd(), k = rd();
  for (int i = 1; i <= n; i++) a[i] = rd();
  for (int i = 1; i <= n; i++) b[i] = rd();
  long long l = 0, r = 1e12, ans = 0;
  while (l <= r) {
    long long mid = (l + r) >> 1;
    pair<long long, int> tp = calc(mid);
    if (tp.second <= k)
      ans = tp.first + (long long)k * mid, l = mid + 1;
    else
      r = mid - 1;
  }
  cout << ans << '\n';
}

```