#include using namespace std; const int MAXN = 2000; int n, s[MAXN + 1], p[MAXN], e[MAXN], a[MAXN]; // DP[i][j] = maximum free time available up to s_i when having studied for (j <= i) of exam 0, 1, ..., (i-1). int DP[MAXN + 1][MAXN + 1]; int main() { cin >> n; for (int i = 0; i < n; i++) cin >> s[i] >> p[i] >> e[i] >> a[i]; s[n] = 1000000000; // 1e9 DP[0][0] = s[0]; for (int exam_id = 0; exam_id < n; exam_id++) { // Initialization of the next layer: for (int studied = 0; studied <= exam_id + 1; studied++) DP[exam_id + 1][studied] = -1; for (int studied = 0; studied <= exam_id; studied++) { if (DP[exam_id][studied] < 0) continue; // Now, we can study for exam exam_id if time_left >= a[i]. if (DP[exam_id][studied] >= a[exam_id]) { DP[exam_id + 1][studied + 1] = max( DP[exam_id + 1][studied + 1], (DP[exam_id][studied] - a[exam_id]) + (s[exam_id + 1] - p[exam_id]) ); } // We can also not study for exam exam_id. DP[exam_id + 1][studied] = max( DP[exam_id + 1][studied], (DP[exam_id][studied]) + (s[exam_id + 1] - e[exam_id]) ); } } #ifdef DEBUG for (int i = 0; i <= n; i++) { for (int j = 0; j <= i; j++) cout << DP[i][j] << " "; cout << endl; } #endif int result = n; while (DP[n][result] < 0) result--; cout << result << endl; return 0; }