В недавно образовавшейся компании «NERC» (New Era Russian Coders), разумеется, есть бухгалтерия. И их очень беспокоит финансовое состояние компании. Особенно им не хочется, чтобы случился кассовый разрыв — ситуация, в которой требуется выплатить больше денег, чем есть сейчас на счёте.
На данный момент на счёте компании находится $$$s$$$ рублей. Главный бухгалтер подготовил план операций на $$$m$$$ ближайших дней. На этот период запланированы $$$n$$$ операций по получению и переводу денег.
Для каждой операции известно на сколько после её выполнения изменяется счет компании, однако точная дата операции неизвестны. Деньги, переведённые клиентами, могут поступить на счёт не сразу, с другой стороны, требования оплатить счета могут поступить внезапно. Для каждой операции, таким образом, известен лишь диапазон дней, в которые эта операция может осуществится. Если несколько операций выполняются в один и тот же день, они могут оказаться выполнены в любом порядке.
Помогите бухгалтерии проверить, верно ли, что при любой возможной последовательности выполнения операций не произойдёт кассового разрыва.
В первой строке через пробел заданы числа $$$n$$$, $$$m$$$ и $$$s$$$ — количество платежей, количество дней в плане и исходное количество денег на счете ($$$1 \leqslant n, m \leqslant 1000$$$; $$$1 \leqslant s \leqslant 10^6$$$).
В $$$i$$$-й из следующих $$$n$$$ строк задано описание $$$i$$$-го платежа в формате «$$$\mathtt{count}~\mathtt{from}~\mathtt{to}$$$», означающее, что в какой-то из дней с $$$\mathtt{from}$$$ по $$$\mathtt{to}$$$, включительно, счет изменится на $$$\mathtt{count}$$$ рублей ($$$-10^6 \leqslant \mathtt{count} \leqslant 10^6$$$; $$$1 \leqslant \mathtt{from} \leqslant \mathtt{to} \leqslant m$$$).
Выведите «YES», если в процессе выполнения операций может произойти кассовый разрыв, и «NO», если такая ситуация невозможна.
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
В первом примере есть единственный перевод со счета, и при этом перед ним заведомо будет хотя бы $$$100$$$ рублей, изначально имевшихся на счете, то есть кассовый разрыв невозможен.
Во втором примере могло случиться так, что оба перевода со счета: на $$$100$$$ рублей и на $$$1$$$ рубль, будут запрошены во второй день, раньше всех остальных переводов. В таком случае на момент второго из них денег на счету уже не останется — это кассовый разрыв.
