#include int n, result, a[2000], time_passing[2000], time_failing[2000], DP[2001][2001]; // DP[i][j] = maximum free time available up to s_i when having studied for (j <= i) of exam 0, 1, ..., (i-1). int main() { std::cin >> n; // Assume s[i] = p[i]. for (int i = 0, si; i < n; i++) { std::cin >> si >> time_passing[i] >> time_failing[i] >> a[i]; if (i) time_passing[i-1] = si - time_passing[i-1], time_failing[i-1] = si - time_failing[i-1]; else DP[0][0] = si; } for (int i = 0; i < n; i++) { for (int j = 0; j <= i; j++) DP[i + 1][j] = DP[i][j] < 0 ? -1 : DP[i][j] + time_failing[i]; // Do not study for exam i: DP[i + 1][i + 1] = -1; for (int j = 0; j <= i + 1; j++) if (DP[i][j] >= a[i]) DP[i + 1][j + 1] = std::max(DP[i + 1][j + 1], DP[i][j] - a[i] + time_passing[i]); // Now, we can study for exam i if time_left >= a[i]. } for (result = n; result > 0 && DP[n][result] < 0; result--); std::cout << result << std::endl; }