Задача №114808. Кассовый разрыв
В недавно образовавшейся компании «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 », если такая ситуация невозможна.
В первом примере есть единственный перевод со счета, и при этом перед ним заведомо будет хотя бы \(100\) рублей, изначально имевшихся на счете, то есть кассовый разрыв невозможен.
Во втором примере могло случиться так, что оба перевода со счета: на \(100\) рублей и на \(1\) рубль, будут запрошены во второй день, раньше всех остальных переводов. В таком случае на момент второго из них денег на счету уже не останется — это кассовый разрыв.
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