#include <bits/stdc++.h>
using namespace std;
int n, K;
int A[2222], B[2222];
int C[2222][2222];
double D[2222][2222];
void Calc(long long c) {
  int i, j;
  for (i = 1; i <= n; i++) {
    for (j = i; j <= n; j++) {
      D[i][j] = D[i][j - 1], C[i][j] = C[i][j - 1];
      if (D[i][j] > D[i - 1][j] ||
          (D[i][j] == D[i - 1][j] && C[i][j] > C[i - 1][j]))
        D[i][j] = D[i - 1][j], C[i][j] = C[i - 1][j];
      if (D[i][j] > D[i - 1][j - 1] + A[i] + B[j] - c ||
          (D[i - 1][j - 1] + A[i] + B[j] - c == D[i][j] &&
           C[i][j] > C[i - 1][j - 1] + 1)) {
        D[i][j] = D[i - 1][j - 1] + A[i] + B[j] - c;
        C[i][j] = C[i - 1][j - 1] + 1;
      }
    }
  }
}
int main() {
  int i;
  long long b = 0, e = 2e9, r;
  scanf("%d%d", &n, &K);
  for (i = 1; i <= n; i++) scanf("%d", &A[i]);
  for (i = 1; i <= n; i++) scanf("%d", &B[i]);
  while (b <= e) {
    long long mid = (b + e) >> 1;
    Calc(mid);
    if (C[n][n] <= K) {
      b = mid + 1;
      r = D[n][n] + K * mid;
    } else
      e = mid - 1;
  }
  printf("%lld\n", r);
}
