#include <bits/stdc++.h>
using namespace std;
pair<long long, int> dp[2500][2500];
pair<long long, int> solve(vector<long long> &a, vector<long long> &b,
                           long long fine) {
  int n = a.size();
  for (int i = 0; i <= n; ++i)
    for (int j = 0; j <= n; ++j) dp[i][j] = {-1e18, 1e9};
  for (int i = 0; i <= n; ++i) dp[0][i] = {0, 0};
  pair<long long, int> ans = {0, 0};
  for (int i = 0; i < n; ++i) {
    pair<long long, int> tut = {0, 0};
    dp[i + 1][0] = dp[i][0];
    for (int j = 0; j < n; ++j) {
      dp[i + 1][j + 1] = dp[i][j + 1];
      if (j >= i) {
        pair<long long, int> var = tut;
        if (a[i] + b[j] + fine > 0) {
          var.first += a[i] + b[j] + fine;
          var.second--;
        }
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], var);
        ans = max(ans, dp[i + 1][j + 1]);
      }
      tut = max(tut, dp[i][j + 1]);
    }
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<long long> a(n), b(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    a[i] *= -1;
  }
  for (int i = 0; i < n; ++i) {
    cin >> b[i];
    b[i] *= -1;
  }
  long long L = -2000000007, R = 2000000007;
  long long profit = 0;
  while (R - L > 1) {
    long long M = (L + R) / 2;
    pair<long long, int> ans = solve(a, b, M);
    if (-ans.second <= k) {
      L = M;
      profit = ans.first;
    } else
      R = M;
  }
  cout << -(profit - L * k);
}
