#include using namespace std; // DP[i][j] = maximum free time available up to s_i when having studied for (j <= i) of exam 0, 1, ..., (i-1). int n, result, a[2000], time_passing[2000], time_failing[2000], DP[2001][2001]; int main() { cin >> n; // Assume s[i] = p[i]. for (int i = 0, si; i < n; i++) { 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++) { // Doe wat stoms: kijk of ik examen k-1 kan halen, als ik `i` nu doe. int extra_time = 0; for (int k = i + 1; k <= n; k++) { if (DP[i][j] + extra_time >= a[i]) DP[k][j + 1] = max(DP[k][j + 1], DP[i][j] + extra_time - a[k-1] + time_passing[k-1]); extra_time += time_failing[k-1]; } } } /* for (int i = 0; i <= n; i++) { for (int j = 0; j <= i; j++) cerr << DP[i][j] << " "; cerr << endl; } */ for (result = n; result > 0 && DP[n][result] < 0; result--); cout << result << endl; }