OIG III - klo

// https://szkopul.edu.pl/problemset/problem/UUw6ABmeLv0dpfsviYlhdnnz/site/?key=statement
// III OIG 3 etap

#include <cstdint>
#include <iostream>
#include <limits.h>

constexpr int sizik = 1000 * 1001;
constexpr int INF = INT16_MAX;

int dp[sizik][2];

int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    int n, k, s;
    std::cin >> n >> k >> s;

    dp[0][0] = 0;
    for (int i = 1; i <= s; i++) {
        dp[i][0] = INF;
    }

    for (int x = 1; x <= n; x++) {
        int a;
        std::cin >> a;

        for (int i = 0; i <= s; i++) {
            dp[i][x % 2] = dp[i][(x - 1) % 2];
        }

        for (int i = 0; i <= s - a; i++) {
            if (dp[i][(x - 1) % 2] != INF) {
                dp[i + a][(x % 2)] = std::min( //
                    dp[i + a][(x - 1) % 2], dp[i][(x - 1) % 2] + 1 //
                );
            }
        }
    }

    int ans = 0;

    for (int i = s; i >= 0; i--) {
        if (dp[i][n % 2] <= k) {
            ans = i;
            break;
        }
    }

    std::cout << ans << '\n';

    return 0;
}