| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 104 | 61 | 50 | 59.524% |
A recently founded "NERC" (New Era Russian Coders) company, of course, has an accounting department. And they are very concerned about the budget of the company. In particular, they don't want the company to experience a cash gap --- a condition where they need to pay more money than they have in their account now.
At the moment the company has $s$ euros on its account. The chief accountant has prepared a plan of transactions for $m$ following days. During this period $n$ transactions are planned.
For each transaction the change it makes to the company's account is known, but the exact date of the operation is unknown. Money transferred by clients may not be credited to the account immediately, and on the other hand, a claim to pay a bill can suddenly be received. For each transaction, only the range of days the transaction can happen is known in advance. If several transactions would happen on the same day, they can be performed in any order.
Help the accounting department to check if there exists an order of transactions such that the company will experience a cash gap.
The first line contains integers $n,ドル $m$ and $s$ --- the number of payments, the number of days in the plan and the initial amount of money the company has (1ドル \leqslant n, m \leqslant 1000$; 1ドル \leqslant s \leqslant 10^6$).
The $i$-th of the following $n$ lines contains a description of the $i$-th payment in the following format: "$\mathtt{count}~\mathtt{from}~\mathtt{to}$", which means that on any day from $\mathtt{from}$ to $\mathtt{to},ドル the amount of money will be changed by $\mathtt{count}$ euros ($-10^6 \leqslant \mathtt{count} \leqslant 10^6$; 1ドル \leqslant \mathtt{from} \leqslant \mathtt{to} \leqslant m$).
Print "YES" if a cash gap can occur, or "NO" if such situation is impossible.
4 3 100 100 1 2 -100 1 2 1 2 3 0 3 3
NO
4 3 100 100 1 2 -100 1 2 1 2 3 -1 2 2
YES
In the first example there is a single transfer from the account, and thus before it there will be at least 100ドル$ euros available in the account, so the cash gap is impossible.
In the second example, it could happen that both transfers from the account (for 100ドル$ euros and for 1ドル$ euro) will be requested on the second day, before all other transactions. In this case by the time the second transaction occurs there will be no money left on the account --- it's a cash gap.