#include using namespace std; const int oo = 0x3f3f3f3f; const double eps = 1e-9; const double PI = 2.0 * acos(0.0); typedef long long ll; typedef unsigned long long ull; typedef pair pii; typedef vector vi; typedef vector vs; #define sz(c) int((c).size()) #define all(c) (c).begin(), (c).end() #define FOR(i,a,b) for (int i = (a); i < (b); i++) #define FORS(i,a,b,s) for (int i = (a); i < (b); i=i+(s)) #define FORD(i,a,b) for (int i = int(b)-1; i >= (a); i--) #define FORIT(i,c) for (__typeof__((c).begin()) i = (c).begin(); i != (c).end(); i++) int s[3000]; int ep[3000]; int eu[3000]; int st[3000]; vector exSt; int dp[3000][3000]; int main(){ int n; cin >> n; eu[0] = 0; FOR(i,1,n+1){ cin >> s[i] >> ep[i] >> eu[i] >> st[i]; } // number of exams, number of passed exams, maximum number of time available. FOR(i,0,n+3) FOR(j,0,n+2) dp[i][j] = -oo; dp[0][0] = 0; int mm = 0; FOR(i,1,n+1) { dp[i][0] = eu[i]; // bug! But works in all samples ... FOR(j,1,i+2){ int nt = s[i] - eu[i-1]; // base option is not to study for i, which gives us more time dp[i][j] = dp[i-1][j] + nt; // actually to the exam if (dp[i-1][j-1] + nt >= st[i]){ nt -= st[i]; nt += eu[i] - ep[i]; if (dp[i-1][j-1] + nt > dp[i-1][j]) dp[i][j] = dp[i-1][j-1] + nt; } if (dp[i][j] >= 0 && j > mm) mm = j; } } cout << mm << endl; }