#include <bits/stdc++.h>
using namespace std;
int n, k, a[2310], b[2310], mxx, mnn, mx[2310][2310], mn[2310][2310], st, en,
    mid, flag;
long long res[2310][2310], sz;
int calc(int c) {
  memset(res, 0, sizeof res);
  memset(mx, 0, sizeof mx);
  memset(mn, 0, sizeof mn);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
      res[i][j] = res[i - 1][j - 1] + b[i] + a[j] - c;
      mx[i][j] = 1 + mx[i - 1][j - 1];
      mn[i][j] = 1 + mn[i - 1][j - 1];
      if (res[i][j] > res[i][j - 1]) {
        res[i][j] = res[i][j - 1];
        mx[i][j] = mx[i][j - 1];
        mn[i][j] = mn[i][j - 1];
      }
      if (res[i][j] == res[i][j - 1]) {
        mx[i][j] = max(mx[i][j], mx[i][j - 1]);
        mn[i][j] = min(mn[i][j], mn[i][j - 1]);
      }
      if (j != i) {
        if (res[i][j] > res[i - 1][j]) {
          res[i][j] = res[i - 1][j];
          mx[i][j] = mx[i - 1][j];
          mn[i][j] = mn[i - 1][j];
        }
        if (res[i][j] == res[i - 1][j]) {
          mx[i][j] = max(mx[i][j], mx[i - 1][j]);
          mn[i][j] = min(mn[i][j], mn[i - 1][j]);
        }
      }
    }
  }
  mxx = mx[n][n];
  mnn = mn[n][n];
  sz = res[n][n];
  if (k <= mxx && mnn <= k) return 0;
  if (mnn > k) return 1;
  if (mxx < k) return -1;
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
  st = 0;
  en = 2000000100;
  while (1) {
    mid = st + (en - st >> 1);
    flag = calc(mid);
    if (flag == 0) {
      printf("%I64d", sz + 1LL * mid * k);
      break;
    } else {
      if (flag == 1)
        en = mid;
      else
        st = mid;
    }
  }
}
