Exam Study Planning

시간 제한1초메모리 제한1024 MB

요약
겹치지 않는 시험 일정이 주어질 때, 각 시험을 준비해 일찍 끝내 통과할 수 있는 최대 개수를 구한다.
난이도

어려움10점 중 8점

유형
동적 계획법, 그리디, 정렬
정답자
아직 제출이 없습니다

문제

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 00, 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.

예제2

  1. 예제 1

    입력
    3
10 20 30 5
30 50 100 15
100 101 200 50
    예상 출력
    3

  2. 예제 2

    입력
    3
1000 1001 1002 1000
1003 1004 1005 500
1006 1007 1008 500
    예상 출력
    2