시험 공부 계획

오늘 볼 시험이 아주 많은데 아직 어느 시험도 준비하지 못했다. 경험상 시험 공부를 충분히 하면 제한 시간보다 훨씬 일찍 합격한다는 것을 알고 있다. 또한 각 시험을 제한 시간 안에 합격하려면 공부를 얼마나 해야 하는지도 정확히 알고 있다. 공부 시간이 그보다 부족하면 확실히 떨어진다.

대학교 규정상 시험은 모두 응시해야 한다. 합격이 확실하다고 알고 있는 경우에만 시험 도중에 나갈 수 있다.

공부는 시각 $0$부터 시작할 수 있지만, 시험을 보고 있지 않은 동안에만 공부할 수 있다. 한 시험의 공부를 연속된 시간에 할 필요는 없으며, 중간에 멈췄다가 다시 이어서 할 수 있다.

각 시험의 시작 시각, 소요 시간, 필요한 공부 시간, 공부한 뒤 끝나는 시각을 포함한 전체 시험 일정이 주어질 때, 최대 몇 개의 시험에 합격할 수 있는지 구하시오.

입력은 다음과 같이 주어진다.

• 첫째 줄에 응시해야 하는 시험의 개수 $n$ ($1 \leq n \leq 2000$)이 주어진다.

• 둘째 줄부터 $n$개의 줄에 걸쳐 $i$번째 줄에는 시험을 나타내는 정수 네 개가 주어진다.

  • $s_i$ ($0 \leq s_i$): $i$번째 시험의 시작 시각
  • $p_i$ ($s_i < p_i$): 공부한 뒤에 응시하면 $i$번째 시험이 끝나는 시각
  • $e_i$ ($p_i \leq e_i \leq 10^9$): 공부하지 않고 응시하면 $i$번째 시험이 끝나는 시각
  • $a_i$ ($1 \leq a_i \leq 10^9$): $i$번째 시험을 준비하는 데 필요한 시간

시험은 시작 시각의 오름차순으로 주어지며 서로 겹치지 않는다. 즉 $1 \leq i < n$인 모든 $i$에 대해 $e_i \leq s_{i+1}$이 성립한다.

합격할 수 있는 시험의 최대 개수를 출력한다.