#include #include typedef long long int ll; using namespace std; #if defined(DEBUG) #include #include #define DLOG(...) cerr << dbgFormat(__VA_ARGS__) << endl #define DCALL(func, ...) func(__VA_ARGS__) template string dbgFormat(const char* fmt, Args... args) { size_t len = snprintf(nullptr, 0, fmt, args...); char buf[len + 1]; snprintf(buf, len + 1, fmt, args...); return string(buf); } #else // defined(DEBUG) #define DLOG(...) #define DCALL(func, ...) #endif // defined(DEBUG) // ---------------------------------------------------------------------- // ---------------------------------------------------------------------- int main(int argc, char *argv[]) { #if defined(DEBUG) // GDB on Cygwin ignores redirection at run command. if (argc == 2) dup2(open(argv[1], 0), 0); #else // For performance. We should not use C-style stdio functions ios_base::sync_with_stdio(false); cin.tie(nullptr); #endif cout << setprecision(20); int N, M, K; cin >> N >> M >> K; vector> rec(N+1, vector(K+1)); rec.at(0).at(0) = true; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { int a; cin >> a; for (int k = 0; k+a <= K; k++) { if (rec.at(i).at(k)) rec.at(i+1).at(k+a) = true; } } } int i = K; while (i >= 0 && !rec.at(N).at(i)) i--; if (i < 0) cout << "-1\n"; else cout << K - i << "\n"; return 0; }