#include #ifdef DEBUG #include "cpp-dump/dump.hpp" #define dump(...) cpp_dump(__VA_ARGS__) #else #define dump(...) #endif using namespace std; typedef long long ll; void solve() { ll n,k; cin >> n >> k; vector A(n), B(n), C(n); for (ll i = 0; i < n; ++i) cin >> A[i]; for (ll i = 0; i < n; ++i) cin >> B[i]; for (ll i = 0; i < n; ++i) cin >> C[i]; vector> dp(n+3, vector(k+3,0)); dp[0][0] = 0; // i本目までj個塩でトッピングするときの最大値 for (ll i = 0; i < n; ++i) { for (ll j = 0; j < k; ++j) { if (j > i) continue; dp[i+1][j] = max(dp[i+1][j], dp[i][j]+A[i]+C[i]); dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+A[i]+B[i]); } } dump(dp); cout << dp[n][k] << endl; } int main() { solve(); return 0; }