Exam Study Planning

You have a lot of exams today, and you have not prepared for any of them yet. From experience, you know that if you study enough for an exam, you will pass it quickly, well within the time limit. You also know exactly how much study time each exam needs to pass within its time limit. If you study less than that, you will fail.

Your university requires you to attend all of your exams. You may leave an exam early only if you know for sure that you passed it.

You may start studying at time $0$, but you can only study while you are not taking an exam. Studying for an exam does not have to happen in one contiguous block. You may stop and resume it.

Given the full exam schedule, including when each exam starts, how long it takes, how long you need to study for it, and how quickly you can finish an exam you studied for, how many exams can you pass at most?

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.