1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5  6 int L, N, B; 7 int f[10001][1001]; 8  9 inline int read()10 {11     int x = 0, f = 1;12     char ch = getchar();13     for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1;14     for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘;15     return x * f;16 }17 18 struct node19 {20     int x, w, f, c;21 }p[10001];22 23 inline bool cmp(node x, node y)24 {25     return x.x < y.x;26 }27 28 inline int max(int x, int y)29 {30     return x > y ? x : y;31 }32 33 int main()34 {35     int i, j;36     L = read();37     N = read();38     B = read();39     for(i = 1; i <= N; i++)40     {41         p[i].x = read();42         p[i].w = read();43         p[i].f = read();44         p[i].c = read();45         p[i].w += p[i].x;46     }47     std::sort(p + 1, p + N + 1, cmp);48     memset(f, -1, sizeof(f));49     for(i = 0; i <= B; i++) f[0][i] = 0;50     for(i = 1; i <= N; i++)51         for(j = B; j >= p[i].c; j--)52             if(f[p[i].x][j - p[i].c] ^ -1)53                 f[p[i].w][j] = max(f[p[i].w][j], f[p[i].x][j - p[i].c] + p[i].f);54     printf("%d\n", f[L][B]);55     return 0;56 }