#include #include #include #include using namespace std; long long solve() { int N, D, K; cin >> N >> D >> K; vector A(N), C(N); for (int i = 0; i < N; i++) cin >> A[i]; for (int i = 0; i < N; i++) cin >> C[i]; const long long INF = LLONG_MIN/10; vector> dp(D + 1, vector(K + 1, INF)); dp[0][0] = 0; for (int i = 0; i < N; i++) { vector> ndp(D + 1, vector(K + 1, INF)); for (int d = 0; d <= D; d++) { for (int k = 0; k <= K; k++) { ndp[d][k] = dp[d][k]; // 配列のコピー } } int a = A[i]; int c = C[i]; for (int d = 0; d + 1 <= D; d++) { for (int k = 0; k <= K; k++) { int nk = min(K, k + c); ndp[d + 1][nk] = max(ndp[d + 1][nk], dp[d][k] + a); } } dp = ndp; } sort(C.begin(), C.end()); long long csum = 0; for (int i = N - D; i < N; i++) { csum += C[i]; } if (csum < K) { return false; } return dp[D][K]; } int main() { cout << solve() << endl; return 0; }