#include <bits/stdc++.h>
using namespace std;
namespace FI {
const int SIZE = 1 << 18 | 1;
char buf[SIZE], *front, *back;
void Char(char &c) {
  if (front == back) back = (front = buf) + fread(buf, 1, SIZE, stdin);
  c = (front == back) ? (char)EOF : *front++;
}
template <typename T>
void Num(T &x) {
  char c;
  int f = 1;
  for (Char(c); c > '9' || c < '0'; Char(c))
    if (c == '-') f = -1;
  for (x = 0; c >= '0' && c <= '9'; Char(c)) x = x * 10 + c - '0';
  x *= f;
}
}  // namespace FI
const int maxn = 500000 + 47;
const long long inf = 1e10;
int n, k;
long long L, R;
long long a[maxn], b[maxn];
long long ta[maxn], tb[maxn];
priority_queue<long long, vector<long long>, greater<long long> > q1;
priority_queue<long long> q2;
int main() {
  FI::Num(n), FI::Num(k);
  for (int i = (1); i <= (n); i++) FI::Num(a[i]);
  for (int i = (1); i <= (n); i++) FI::Num(b[i]);
  L = -inf, R = inf;
  while (L <= R) {
    int mid = (L + R) >> 1;
    for (int i = (1); i <= (n); i++) ta[i] = a[i] + mid;
    for (int i = (1); i <= (n); i++) tb[i] = b[i] + mid;
    while (!q1.empty()) q1.pop();
    while (!q2.empty()) q2.pop();
    long long res = 0;
    int cnt0 = 0, cnt1 = 0;
    for (int i = (1); i <= (n); i++) {
      q1.push(ta[i]);
      long long t1 = q1.top();
      long long t2 = q2.empty() ? -1e18 : q2.top();
      long long r1 = t1 + tb[i], r2 = tb[i] - t2;
      if (r1 < r2 && r1 < 0) res += r1, cnt0++, q1.pop(), q2.push(tb[i]);
      if (r1 >= r2 && r2 < 0) res += r2, q2.pop(), q2.push(tb[i]);
    }
    while (!q1.empty()) q1.pop();
    while (!q2.empty()) q2.pop();
    for (int i = (1); i <= (n); i++) {
      q1.push(ta[i]);
      long long t1 = q1.top();
      long long t2 = q2.empty() ? -1e18 : q2.top();
      long long r1 = t1 + tb[i], r2 = tb[i] - t2;
      if (r1 <= r2 && r1 < 0) cnt1++, q1.pop(), q2.push(tb[i]);
      if (r1 > r2 && r2 < 0) q2.pop(), q2.push(tb[i]);
    }
    if (cnt0 <= k && cnt1 >= k) {
      printf("%lld\n", res - 2LL * k * mid);
      break;
    } else {
      if (cnt0 > k)
        L = mid + 1;
      else
        R = mid - 1;
    }
  }
  return 0;
}

### Prompt

Your challenge is to write 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;
namespace FI {
const int SIZE = 1 << 18 | 1;
char buf[SIZE], *front, *back;
void Char(char &c) {
  if (front == back) back = (front = buf) + fread(buf, 1, SIZE, stdin);
  c = (front == back) ? (char)EOF : *front++;
}
template <typename T>
void Num(T &x) {
  char c;
  int f = 1;
  for (Char(c); c > '9' || c < '0'; Char(c))
    if (c == '-') f = -1;
  for (x = 0; c >= '0' && c <= '9'; Char(c)) x = x * 10 + c - '0';
  x *= f;
}
}  // namespace FI
const int maxn = 500000 + 47;
const long long inf = 1e10;
int n, k;
long long L, R;
long long a[maxn], b[maxn];
long long ta[maxn], tb[maxn];
priority_queue<long long, vector<long long>, greater<long long> > q1;
priority_queue<long long> q2;
int main() {
  FI::Num(n), FI::Num(k);
  for (int i = (1); i <= (n); i++) FI::Num(a[i]);
  for (int i = (1); i <= (n); i++) FI::Num(b[i]);
  L = -inf, R = inf;
  while (L <= R) {
    int mid = (L + R) >> 1;
    for (int i = (1); i <= (n); i++) ta[i] = a[i] + mid;
    for (int i = (1); i <= (n); i++) tb[i] = b[i] + mid;
    while (!q1.empty()) q1.pop();
    while (!q2.empty()) q2.pop();
    long long res = 0;
    int cnt0 = 0, cnt1 = 0;
    for (int i = (1); i <= (n); i++) {
      q1.push(ta[i]);
      long long t1 = q1.top();
      long long t2 = q2.empty() ? -1e18 : q2.top();
      long long r1 = t1 + tb[i], r2 = tb[i] - t2;
      if (r1 < r2 && r1 < 0) res += r1, cnt0++, q1.pop(), q2.push(tb[i]);
      if (r1 >= r2 && r2 < 0) res += r2, q2.pop(), q2.push(tb[i]);
    }
    while (!q1.empty()) q1.pop();
    while (!q2.empty()) q2.pop();
    for (int i = (1); i <= (n); i++) {
      q1.push(ta[i]);
      long long t1 = q1.top();
      long long t2 = q2.empty() ? -1e18 : q2.top();
      long long r1 = t1 + tb[i], r2 = tb[i] - t2;
      if (r1 <= r2 && r1 < 0) cnt1++, q1.pop(), q2.push(tb[i]);
      if (r1 > r2 && r2 < 0) q2.pop(), q2.push(tb[i]);
    }
    if (cnt0 <= k && cnt1 >= k) {
      printf("%lld\n", res - 2LL * k * mid);
      break;
    } else {
      if (cnt0 > k)
        L = mid + 1;
      else
        R = mid - 1;
    }
  }
  return 0;
}

```