#include <cstdio>
#include <cctype>

struct IO {
  static const int BUFSIZE = 1 << 20;
  char buf[BUFSIZE], *p1, *p2;
  char pbuf[BUFSIZE], *pp;
  
  IO() : p1(buf), p2(buf), pp(pbuf) {}
  ~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
  
  char getchar() {
    if (p1 == p2) {
      p2 = (p1 = buf) + fread(buf, 1, BUFSIZE, stdin);
      if (p1 == p2) return EOF;
    }
    return *p1++;
  }
  
  void putchar(char ch) {
    if (pp - pbuf == BUFSIZE) fwrite(pbuf, 1, BUFSIZE, stdout), pp = pbuf;
    *pp++ = ch;
  }
  
  template <typename T> T read() {
    T res = 0, f = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
    for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
    return res * f;
  }
  
  template <typename T> void write(T x, char ed = '\n') {
    if (x < 0) x = -x, putchar('-');
    static int sta[sizeof(T) << 2], top = 0;
    do {
      sta[++top] = x % 10;
      x /= 10;
    } while (x);
    while (top) {
      putchar(sta[top--] ^ 48);
    }
    putchar(ed);
  }
} io;

#include <algorithm>
#include <tuple>

const int MAXN = 1e6 + 10;

struct Card {
  int front, back;
  bool flipped = false;
  
  int flip() {
    std::swap(front, back);
    flipped = !flipped;
    return front;
  }
  
  void reset() {
    if (flipped) std::swap(front, back);
    flipped = false;
  }
} card[MAXN];

int n, m;
int a[MAXN], b[MAXN];
int maxx = -1, minn = 0x7fffffff;

struct SegmentTree {
  struct NODE {
    int maxx, minn;
    int maxi, mini;
  } node[MAXN << 2];
  
  #define ls(root) root << 1
  #define rs(root) root << 1 | 1
  void PushUp(int root) {
    if (node[ls(root)].maxx > node[rs(root)].maxx) {
      node[root].maxx = node[ls(root)].maxx;
      node[root].maxi = node[ls(root)].maxi;
    } else {
      node[root].maxx = node[rs(root)].maxx;
      node[root].maxi = node[rs(root)].maxi;
    }
    if (node[ls(root)].minn < node[rs(root)].minn) {
      node[root].minn = node[ls(root)].minn;
      node[root].mini = node[ls(root)].mini;
    } else {
      node[root].minn = node[rs(root)].minn;
      node[root].mini = node[rs(root)].mini;
    }
  }
  
  void AddSingle(int root, int lt, int rt, int pos, int val) {
    if (lt == rt) {
      node[root].maxx += val;
      node[root].minn += val;
      node[root].maxi = node[root].mini = pos;
      return ;
    }
    int mid = lt + ((rt - lt) >> 1);
    if (pos <= mid) {
      AddSingle(ls(root), lt, mid, pos, val);
    } else {
      AddSingle(rs(root), mid + 1, rt, pos, val);
    }
    PushUp(root);
  }
  
  void SetSingle(int root, int lt, int rt, int pos, int val) {
    if (lt == rt) {
      node[root].maxx = node[root].minn = val;
      node[root].mini = node[root].maxi = pos;
      return ;
    }
    int mid = lt + ((rt - lt) >> 1);
    if (pos <= mid) {
      SetSingle(ls(root), lt, mid, pos, val);
    } else {
      SetSingle(rs(root), mid + 1, rt, pos, val);
    }
  }
  
  std::pair<int, int> GetSeqMax(int root, int lt, int rt, int lq, int rq) {
    if (lt == lq && rt == rq) {
      return {node[root].maxx, node[root].maxi};
    }
    int mid = lt + ((rt - lt) >> 1);
    if (rq <= mid) {
      return GetSeqMax(ls(root), lt, mid, lq, rq);
    } else if (lq > mid) {
      return GetSeqMax(rs(root), mid + 1, rt, lq, rq);
    } else {
      std::pair<int, int> lson = GetSeqMax(ls(root), lt, mid, lq, mid), rson = GetSeqMax(rs(root), mid + 1, rt, mid + 1, rq);
      if (lson.first > rson.first) return lson;
      return rson;
    }
  }
  
  std::pair<int, int> GetSeqMin(int root, int lt, int rt, int lq, int rq) {
    if (lt == lq && rt == rq) {
      return {node[root].minn, node[root].mini};
    }
    int mid = lt + ((rt - lt) >> 1);
    if (rq <= mid) {
      return GetSeqMin(ls(root), lt, mid, lq, rq);
    } else if (lq > mid) {
      return GetSeqMin(rs(root), mid + 1, rt, lq, rq);
    } else {
      std::pair<int, int> lson = GetSeqMin(ls(root), lt, mid, lq, mid), rson = GetSeqMin(rs(root), mid + 1, rt, mid + 1, rq);
      if (lson.first < rson.first) return lson;
      return rson;
    }
  }
  
  void reset() {
    for (int i = 1; i <= n; ++i) SetSingle(1, 1, n, i, 0);
  }
} T;

//bool check(int mid) {
//  int flipCnt = 0, maxx = -1, maxi = 0, minn = 0x7fffffff, mini = 0;
//  for (int i = 1; i <= n; ++i) {
//    if (card[i].front > maxx) maxx = card[i].front, maxi = i;
//    if (card[i].front < minn) minn = card[i].front, mini = i;
//    if (maxx - minn > mid) maxx = card[maxi].back, flipCnt++;
//    if (maxx - minn > mid) minn = card[mini].back, flipCnt++;
//    if (maxx - minn > mid) return false;
//    if (flipCnt > m) return false;
//  }
//  return true;
//}

bool check(int mid) {
  T.reset();
  for (int i = 1; i <= n; ++i) card[i].reset();
  
  int flipCnt = 0, maxx = -1, minn = 0x7fffffff, maxi = 0, mini = 0;
  for (int i = 1; i <= n; ++i) {
    T.SetSingle(1, 1, n, i, card[i].front);
    std::tie(maxx, maxi) = T.GetSeqMax(1, 1, n, 1, i);
    std::tie(minn, mini) = T.GetSeqMin(1, 1, n, 1, i);
//    if (card[i].front > maxx) maxx = card[i].front, maxi = i;
//    if (card[i].front < minn) minn = card[i].front, mini = i;
    while (maxx - minn > mid) {
      T.SetSingle(1, 1, n, maxi, /*b[maxi]*/ card[maxi].flip()), flipCnt++;
      std::tie(maxx, maxi) = T.GetSeqMax(1, 1, n, 1, i);
      if (flipCnt > m) return false;
      
      if (maxx - minn <= mid) break;
      
      T.SetSingle(1, 1, n, mini, /*b[mini]*/ card[mini].flip()), flipCnt++;
      std::tie(minn, mini) = T.GetSeqMin(1, 1, n, 1, i);
      if (flipCnt > m) return false;
    }
  } 
  return true;
} 

int main() {
  #ifdef LOCAL
    freopen("!input.in", "r", stdin);
    freopen("!output.out", "w", stdout);
  #else
    freopen("card.in", "r", stdin);
    freopen("card.out", "w", stdout);
  #endif
  
  n = io.read<int>(), m = io.read<int>();
  for (int i = 1; i <= n; ++i) {
    card[i].front = io.read<int>();
    minn = std::min(minn, card[i].front);
    maxx = std::max(maxx, card[i].front);
  }
  for (int i = 1; i <= n; ++i) {
    card[i].back = io.read<int>();
    minn = std::min(minn, card[i].back);
    maxx = std::max(maxx, card[i].back);
  }
  
  int l = 0, r = maxx - minn, ans = -1;
  while (l <= r) {
    int mid = l + ((r - l) >> 1);
    if (check(mid)) {
      ans = mid;
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  
  io.write(ans);
  return 0;
}