30493번 - Exam Study Planning 다국어

문제

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.

제한

힌트