#include <bits/stdc++.h>
using namespace std;
inline void read(int& x) {
  char c11 = getchar();
  x = 0;
  while (!isdigit(c11)) c11 = getchar();
  while (isdigit(c11)) x = x * 10 + c11 - '0', c11 = getchar();
}
const int N = 505010;
int a[N], b[N];
int n, k;
long long Ans = 0;
namespace A {
int h[N], tp = 0;
inline int top() { return tp ? h[1] : 0; }
inline void clear() { tp = 0; }
inline bool empty() { return tp == 0; }
inline void push(int x) {
  h[++tp] = x;
  push_heap(h + 1, h + tp + 1, greater<int>());
}
inline void pop() {
  pop_heap(h + 1, h + tp + 1, greater<int>());
  --tp;
}
}  // namespace A
namespace B {
int h[N], tp = 0;
inline int top() { return tp ? h[1] : 0; }
inline void clear() { tp = 0; }
inline bool empty() { return tp == 0; }
inline void push(int x) {
  h[++tp] = x;
  push_heap(h + 1, h + tp + 1);
}
inline void pop() {
  pop_heap(h + 1, h + tp + 1);
  --tp;
}
}  // namespace B
void calc(int t, int& re) {
  A::clear();
  B::clear();
  re = 0, Ans = (long long)k * t;
  int qwq, pwp;
  for (int i = 1; i <= n; ++i) {
    A::push(a[i]), pwp = 0;
    qwq = A::top() - t + b[i];
    if (!B::empty()) pwp = b[i] - B::top();
    if (qwq <= pwp and qwq < 0) Ans += qwq, A::pop(), B::push(b[i]), ++re;
    if (qwq >= pwp and pwp < 0) Ans += pwp, B::pop(), B::push(b[i]);
  }
}
int main() {
  read(n), read(k);
  for (int i = 1; i <= n; ++i) read(a[i]);
  for (int i = 1; i <= n; ++i) read(b[i]);
  int re;
  long long l = 0, r = 1e11, mid;
  while (l + 2 <= r) {
    mid = l + r >> 1;
    calc(mid, re);
    if (re <= k)
      l = mid;
    else
      r = mid;
  }
  calc(l, re);
  printf("%lld\n", Ans);
  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;
inline void read(int& x) {
  char c11 = getchar();
  x = 0;
  while (!isdigit(c11)) c11 = getchar();
  while (isdigit(c11)) x = x * 10 + c11 - '0', c11 = getchar();
}
const int N = 505010;
int a[N], b[N];
int n, k;
long long Ans = 0;
namespace A {
int h[N], tp = 0;
inline int top() { return tp ? h[1] : 0; }
inline void clear() { tp = 0; }
inline bool empty() { return tp == 0; }
inline void push(int x) {
  h[++tp] = x;
  push_heap(h + 1, h + tp + 1, greater<int>());
}
inline void pop() {
  pop_heap(h + 1, h + tp + 1, greater<int>());
  --tp;
}
}  // namespace A
namespace B {
int h[N], tp = 0;
inline int top() { return tp ? h[1] : 0; }
inline void clear() { tp = 0; }
inline bool empty() { return tp == 0; }
inline void push(int x) {
  h[++tp] = x;
  push_heap(h + 1, h + tp + 1);
}
inline void pop() {
  pop_heap(h + 1, h + tp + 1);
  --tp;
}
}  // namespace B
void calc(int t, int& re) {
  A::clear();
  B::clear();
  re = 0, Ans = (long long)k * t;
  int qwq, pwp;
  for (int i = 1; i <= n; ++i) {
    A::push(a[i]), pwp = 0;
    qwq = A::top() - t + b[i];
    if (!B::empty()) pwp = b[i] - B::top();
    if (qwq <= pwp and qwq < 0) Ans += qwq, A::pop(), B::push(b[i]), ++re;
    if (qwq >= pwp and pwp < 0) Ans += pwp, B::pop(), B::push(b[i]);
  }
}
int main() {
  read(n), read(k);
  for (int i = 1; i <= n; ++i) read(a[i]);
  for (int i = 1; i <= n; ++i) read(b[i]);
  int re;
  long long l = 0, r = 1e11, mid;
  while (l + 2 <= r) {
    mid = l + r >> 1;
    calc(mid, re);
    if (re <= k)
      l = mid;
    else
      r = mid;
  }
  calc(l, re);
  printf("%lld\n", Ans);
  return 0;
}

```