레이팅 미적용You have a lot of exams today! And you have not yet prepared for any of them! At least you know from experience that if you study enough for an exam, you will for sure pass it quickly, well within the allotted time. Even better, you stared so long at the daunting course curricula that you now know exactly how much time you will need to study for each exam in order to pass it within the given time. If you do not study long enough, you will for sure fail it.
As it happens, your university has some weird bureaucratic rules that require you to attend all your exams. The horror! And leaving early is not allowed, unless you know for sure you passed it!
Given the full exam schedule of when each exam starts, how long each exam takes, how much time you need to study for each exam, and how quickly you can finish each exam you studied for, how many exams can you pass at most?
You may start studying at time \(0\), but can only study while not making an exam. The preparation for an exam does not have to be done in a contiguous block of time and may be interrupted.
The input consists of:
- One line with an integer (n) ((1 \leq n\leq 2000)), the number of exams you have to attend.
- (n) lines, the (i)th of which contains four integers describing an exam:
- (s_i) ((0 \leq s_i)), the start time of the (i)th exam,
- (p_i) ((s_i < p_i)), the end time of the (i)th exam if you prepare for it,
- (e_i) ((p_i \leq e_i \leq 10^9)), the end time of the (i)th exam if you do not prepare for it,
- (a_i) ((1 \leq a_i \leq 10^9)), the time needed to prepare the (i)th exam.
The exams are given in ascending order of start time, and do not overlap, i.e. (e_i \leq s_{i+1}) holds for (1 \leq i < n).
Output the maximum number of exams you can pass.
3
10 20 30 5
30 50 100 15
100 101 200 50
3
3
1000 1001 1002 1000
1003 1004 1005 500
1006 1007 1008 500
2