#include #include using namespace std; using namespace atcoder; // 型エイリアス using ll = long long; using i128 = __int128_t; using ldb = long double; using mint = modint998244353; using pll = pair; using tll = tuple; using tll4 = tuple; using vll = vector; using vvll = vector; using vvvll = vector; using vld = vector; using vvld = vector; using vvvdl = vector; using vch = vector; using vvch = vector; using vvvch = vector; using vst = vector; using vvst = vector; using vvvst = vector; using vbo = vector; using vvbo = vector; using vvvbo = vector; using vmi = vector; using vvmi = vector; using vvvmi = vector; using vpll = vector; using vvpll = vector; using vvvpll = vector; using vtll = vector; using vvtll = vector; using vvvtll = vector; using vtll4 = vector; using vvtll4 = vector; using vvvtll4 = vector; // 補助マクロ #define OVERLOAD4(a, b, c, d, e, ...) e #define OVERLOAD6(a, b, c, d, e, f, g, ...) g // rep系 #define REP1(n) for(ll _ = 0 ; _ < (n); _++) #define REP2(i, n) for(ll i = 0; i < (n); i++) #define REP3(i, m, n) for(ll i = (m); i < (n); i++) #define REP4(i, m, n, d) for(ll i = (m); i < (n); i += (d)) #define RREP1(n) for(ll _ = (n) - 1 ; _ >= 0; _--) #define RREP2(i, n) for(ll i = (n) - 1; i >= 0; i--) #define RREP3(i, m, n) for(ll i = (m) - 1; i >= (n); i--) #define RREP4(i, m, n, d) for(ll i = (m) - 1; i >= (n); i -= (d)) #define rep(...) OVERLOAD4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__) #define rrep(...) OVERLOAD4(__VA_ARGS__, RREP4, RREP3, RREP2, RREP1)(__VA_ARGS__) // 入力 template void CIN(T& x) { cin >> x; } template void CIN(T& x, Ts&... xs) { cin >> x; CIN(xs...); } #define LL(...) ll __VA_ARGS__; CIN(__VA_ARGS__) #define LDB(...) ldb __VA_ARGS__; CIN(__VA_ARGS__) #define CHAR(...) char __VA_ARGS__; CIN(__VA_ARGS__) #define STR(...) string __VA_ARGS__; CIN(__VA_ARGS__) #define VEC3(type, name, N) vector name(N); for(auto& x: name) cin >> x #define VEC4(type, name1, name2, N) vector name1(N), name2(N); for(ll i = 0; i < N; i++) cin >> name1[i] >> name2[i] #define VEC5(type, name1, name2, name3, N) vector name1(N), name2(N), name3(N); for(ll i = 0; i < N; i++) cin >> name1[i] >> name2[i] >> name3[i] #define VEC6(type, name1, name2, name3, name4, N) vector name1(N), name2(N), name3(N), name4(N); for(ll i = 0; i < N; i++) cin >> name1[i] >> name2[i] >> name3[i] >> name4[i] #define VEC(...) OVERLOAD6(__VA_ARGS__, VEC6, VEC5, VEC4, VEC3)(__VA_ARGS__) #define VLL(...) VEC(ll, __VA_ARGS__) #define VLD(...) VEC(ldb, __VA_ARGS__) #define VST(...) VEC(string, __VA_ARGS__) #define VVEC4(type, name, N, M) vector> name(N, vector(M)); for(auto& v : name) for(auto& x : v) cin >> x #define VVEC3(type, name, N) VVEC4(type, name, N, N) #define VVEC(...) OVERLOAD4(__VA_ARGS__, VVEC4, VVEC3)(__VA_ARGS__) #define VVLL(...) VVEC(ll, __VA_ARGS__) // 出力 const pair YESNO_STRINGS = {"Yes", "No"}; template void PR(const T& a, const Ts&... b) { cout << a; ((cout << ' ' << b), ...); cout << '\n'; } template void PRS(const Ts&... a) { ((cout << a << ' '), ...); } template void PRC(const Container& c) { bool first = true; for (const auto& x : c) {if (!first) {cout << ' ';} cout << x; first = false; } cout << '\n'; } #define YES PR(YESNO_STRINGS.first) #define NO PR(YESNO_STRINGS.second) bool YN(bool f) { if (f) { YES; return true; } NO; return false; } // 整数系マクロ template T MOD(T n, U m) { return (n % m + m) % m; } template bool ODD(T n) { return MOD(n, 2) == 1; } template bool EVEN(T n) { return MOD(n, 2) == 0; } template T CEIL(T n, U d) { return d < 0 ? CEIL(-n, -d) : (n >= 0 ? (n + d - 1) / d : n / d); } template T FLOOR(T n, U d) { return d < 0 ? FLOOR(-n, -d) : (n >= 0 ? n / d : (n - d + 1) / d); } template T POW(T x, U n) { assert(n >= 0); T ret = 1; while(n > 0) { if (n % 2 == 1) { ret = ret * x; } x *= x; n /= 2; } return ret; } template T FLOG(U n, T x) { T ret = -1, cur = 1; while(cur <= x) { cur *= n; ret++; } return ret; } template T CLOG(U n, T x) { T ret = 0, cur = 1; while(cur < x) { cur *= n; ret++; } return ret; } template T SQRT(T n) { T x = (T)sqrt(n); while((x + 1) * (x + 1) <= n) { x++; } while(x * x > n) { x--; } return x; } template bool BIT(T n, U i) { return (n >> i) & 1; } template ll POPCNT(T n) { return popcount((unsigned long long)n); } template ll DIGSZ(T n) { return to_string(n).size(); } // コンテナ系マクロ #define ALL(v) (v).begin(),(v).end() #define RALL(v) (v).rbegin(),(v).rend() #define SZ(v) (ll)(v).size() template void ADD(T& v, const U& x) { if constexpr (ranges::range) { for (auto& e : v) { ADD(e, x); } } else { v += x; } } template void INC(Container& C) { ADD(C, 1); } template void DEC(Container& C) { ADD(C, -1); } template void UNIQUE(T& A) { sort(A.begin(), A.end()); A.erase(unique(A.begin(), A.end()), A.end()); } template auto SUM(const T& v) { if constexpr (ranges::range) { decltype(SUM(*begin(v))) ret = 0; for (const auto& e : v) { ret += SUM(e); } return ret; } else { return v; } } template ll MAXID(const Container& C) { return distance(C.begin(), max_element(C.begin(), C.end())); } template ll MINID(const Container& C) { return distance(C.begin(), min_element(C.begin(), C.end())); } template ll FINDID(const Container& C, T x) { return distance(C.begin(), find(C.begin(), C.end(), x)); } template ll LBID(const Container& C, T x) { return distance(C.begin(), lower_bound(C.begin(), C.end(), x)); } template ll UBID(const Container& C, T x) { return distance(C.begin(), upper_bound(C.begin(), C.end(), x)); } template auto RLE(const Container& C) { vector> ret; for (const auto& x : C) { if (ret.empty() || x != ret.back().first) { ret.emplace_back(x, 1); } else { ret.back().second++; } } return ret; } template vector CUM(const vector& V) { vector ret(V.size()+1, 0); for (ll i = 0; i < (ll)V.size(); i++) { ret[i+1] = ret[i] + V[i]; } return ret; } template bool ISPAL(C& V) { for (ll i = 0; i < (ll)V.size() / 2; i++) { if (V[i] != V[(ll)V.size() - 1 - i]) return false; } return true; } // 幾何系マクロ template bool INGRID(T x, T y, T H, T W) { return x >= 0 && x < H && y >= 0 && y < W; } template vector TRANSPOSE(vector& G) { vector H(G[0].size(), C(G.size(), 0)); for(ll i = 0; i < (ll)G[0].size(); i++) for(ll j = 0; j < (ll)G.size(); j++) H[i][j] = G[j][i]; return H; } template T EDIST(T x1, T y1, T x2, T y2) { return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2); } template T MDIST(T x1, T y1, T x2, T y2) { return abs(x1 - x2) + abs(y1 - y2); } // その他便利マクロ template bool CHMIN(T& a, U b){ if(a>b){ a=b; return true; } return false; } template bool CHMAX(T& a, U b){ if(a void SORT(Ts&... xs) { vector v = {xs...}; sort(v.begin(), v.end()); int i = 0; ((xs = v[i++]), ...); } // 定数 const ll INF = 4'000'000'000'000'000'000LL; const ll DI[] = {-1, 0, 1, 0}; const ll DJ[] = {0, 1, 0, -1}; const ll DI8[] = {-1, -1, 0, 1, 1, 1, 0, -1}; const ll DJ8[] = {0, 1, 1, 1, 0, -1, -1, -1}; const string DIR = "URDL"; const bool IS_MULTI_CASE = false; void solve() { LL(N, D, K); VLL(A, N); VLL(C, N); vvll dp(D+1, vll(K+1, -INF)); dp[0][0] = 0; rep(i, N) { rrep(j, D) { rep(k, K+1) { if (dp[j][k] == -INF) continue; CHMAX(dp[j+1][min(k+C[i], K)], dp[j][k] + A[i]); } } } if (dp[D][K] == -INF) { NO; } else { PR(dp[D][K]); } } int main() { ios::sync_with_stdio(false); std::cin.tie(nullptr); cout << fixed << setprecision(15); ll T = 1; if (IS_MULTI_CASE) cin >> T; while(T--) { solve(); } }