// #include C { #include #include #include #include #include // } // #include C++ { #include #include #include #include #include #include #include #include #include #include #include #include #include // } using namespace std; // #typedef { typedef long long int64; typedef unsigned long long uint64; typedef pair PII; typedef pair PCC; typedef pair PLL; typedef pair PDD; // } // #parameter{ #ifdef DEBUG_MODE #define TYPE decltype #define RF(filename) {freopen((filename), "r", stdin);} #define WF(filename) {freopen((filename), "w", stdout);} #define DEBUG printf #else #define TYPE __typeof #define RF(filename) {;} #define WF(filename) {;} #define DEBUG(...) #endif // #define { #define SZ(a) ((int)(a).size()) #define X first #define Y second #define MP make_pair #define L(x) ((x)<<1) #define R(x) ((x)<<1 | 1) #define max3(x, y, z) (max(max((x), (y)), (z))) #define min3(x, y, z) (min(min((x), (y)), (z))) #define BIT(x, i) (((x) >> (i)) & 1) #define ALL(it) (it).begin(), (it).end() #define FILL(__space, __val) memset(__space, __val, sizeof(__space)) #define MOVE(__spaceTo, __spaceFrom) memmove(__spaceTo, __spaceFrom, sizeof(__spaceTo)) #define FOR(it, c) for( TYPE((c).begin()) it = (c).begin(); it != (c).end(); it++) ///////////////////////////////////////////////////////////// const double PI = acos(-1.0); const double EPS = 1e-6; #define MAX_N 205 #define MAX_M 1005 #define MAXX 0x3f #define UPPER 2147483647LL #define INF ((1 << 30) - 1) #define BINF ((1LL << 62) - 1LL) #define NONE -1 #define NIL 0 // } ///////////////////////////////////////////////////////////// bool dp[MAX_N][MAX_N][MAX_N]; ///////////////////////////////////////////////////////////// int main(){ RF("input.txt"); // WF("output.txt"); int n, m, K; while (~scanf("%d %d %d", &n, &m, &K)){ FILL(dp, false); for (int i = 0; i < MAX_N; i++) dp[i][0][0] = dp[0][i][0] = true; int res = 0; for (int r = 1; r <= n; r++) for (int c = 1; c <= m; c++){ int w; scanf("%d", &w); for (int k = K; k >= 0; k--){ dp[r][c][k] |= dp[r - 1][c][k] || dp[r][c - 1][k]; if (k >= w) dp[r][c][k] |= dp[r - 1][c][k - w] || dp[r][c - 1][k - w]; if (dp[r][c][k]) res = max(res, k); } } printf("%d\n", res); } return 0; }