D. Порталы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы играете в стратегическую компьютерную игру (да, у нас закончились идеи для легенд задач). В этой игре вы управляете огромной армией, и ваша задача — захватить $$$n$$$ замков противника.

Рассмотрим игровой процесс более подробно. Изначально у вас в управлении армия из $$$k$$$ воинов. Противник контролирует $$$n$$$ замков; для захвата $$$i$$$-го замка вам потребуется $$$a_i$$$ воинов (считается, что каждый захват замка проводится без потерь, поэтому размер армии после захвата не меняется). После захвата каждого замка вы увеличиваете свою армию, нанимая воинов в новом замке — в $$$i$$$-м замке вы сможете нанять $$$b_i$$$ воинов. Помимо захвата замков, в каждом из них можно оставить охрану (только после захвата): если вы оставляете хотя бы одного воина в замке, то этот замок будет считаться охраняемым. У каждого замка есть параметр важности $$$c_i$$$, и успешность вашей стратегии определяется суммарной важностью всех охраняемых замков в конце игры. Оставлять охрану в замке можно двумя способами:

  • если вы находитесь в замке $$$i$$$, вы можете оставить одного воина для охраны замка $$$i$$$;
  • замки связаны $$$m$$$ односторонними порталами. Каждый портал характеризуется двумя номерами соединяемых замков $$$u$$$ и $$$v$$$ (для каждого портала $$$u > v$$$). Порталами можно пользоваться следующим способом: если вы находитесь в замке $$$u$$$, вы можете отправить одного воина охранять замок $$$v$$$ через портал.

Вы захватываете замки по очереди: сначала первый, потом второй, и так далее. После захвата замка $$$i$$$, пока вы не захватили замок $$$i + 1$$$, вы можете нанять воинов в замке $$$i$$$, оставить охрану в замке $$$i$$$, а также воспользоваться любым количеством порталов, ведущих из замка $$$i$$$ в замки с меньшими номерами. После того, как вы захватите следующий замок, эти действия для замка $$$i$$$ будут уже недоступны.

Если в какой-то момент вам не хватает воинов для захвата следующего замка, вы проигрываете. Ваша цель — максимизировать суммарную важность всех охраняемых замков после захвата последнего замка (обратите внимание, что вы можете нанимать воинов в последнем замке после его захвата, оставлять в нем охрану и пользоваться порталами — суммарная важность всех охраняемых замков будет подсчитана после всех ваших действий).

Можете ли вы разработать оптимальную стратегию захвата замков и оставления охраны?

Входные данные

В первой строке входных данных заданы три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \le n \le 5000$$$, $$$0 \le m \le \min(\frac{n(n - 1)}{2}, 3 \cdot 10^5)$$$, $$$0 \le k \le 5000$$$) — количество замков, количество порталов и изначальное количество воинов в вашей армии, соответственно.

Далее следуют $$$n$$$ строк, в $$$i$$$-й из которых содержится описание $$$i$$$-го замка — три целых числа $$$a_i$$$, $$$b_i$$$ и $$$c_i$$$ ($$$0 \le a_i, b_i, c_i \le 5000$$$) — количество воинов, требуемых для захвата замка $$$i$$$, количество воинов, которых можно нанять после захвата, и важность замка, соответственно.

Далее следуют $$$m$$$ строк, в $$$i$$$-й из которых содержится описание $$$i$$$-го портала — два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \le v_i < u_i \le n$$$), соответствующих порталу, который ведет из замка $$$u_i$$$ в замок $$$v_i$$$. Не существует двух одинаковых порталов.

Гарантируется, что размер вашей армии ни при каких условиях не может превысить $$$5000$$$ (то есть $$$k + \sum\limits_{i = 1}^{n} b_i \le 5000$$$).

Выходные данные

Если невозможно захватить все замки ни при каких обстоятельствах, выведите одно целое число $$$-1$$$.

Иначе выведите одно целое число — максимальную суммарную важность всех охраняемых замков в конце игры.

Примеры
Входные данные
4 3 7
7 4 17
3 0 8
11 2 0
13 3 5
3 1
2 1
4 3
Выходные данные
5
Входные данные
4 3 7
7 4 17
3 0 8
11 2 0
13 3 5
3 1
2 1
4 1
Выходные данные
22
Входные данные
4 3 7
7 4 17
3 0 8
11 2 0
14 3 5
3 1
2 1
4 3
Выходные данные
-1
Примечание

Лучшая стратегия в первом примере — следующая:

  1. захватить первый замок;
  2. нанять солдат в первом замке, теперь у вас $$$11$$$ солдат;
  3. захватить второй замок;
  4. захватить третий замок;
  5. нанять солдат в третьем замке, теперь у вас $$$13$$$ солдат;
  6. захватить четвертый замок;
  7. оставить одного воина в четвертом замке, теперь у вас $$$12$$$ солдат.

Эта стратегия (и некоторые другие) дает в результате суммарную важность охраняемых замков, равную $$$5$$$.

Лучшая стратегия во втором примере — следующая:

  1. захватить первый замок;
  2. нанять солдат в первом замке, теперь у вас $$$11$$$ солдат;
  3. захватить второй замок;
  4. захватить третий замок;
  5. нанять солдат в третьем замке, теперь у вас $$$13$$$ солдат;
  6. захватить четвертый замок;
  7. оставить одного воина в четвертом замке, теперь у вас $$$12$$$ солдат;
  8. отправить одного воина в первый замок через третий портал, теперь у вас $$$11$$$ солдат.

Эта стратегия (и некоторые другие) дает в результате суммарную важность охраняемых замков, равную $$$22$$$.

В третьем примере нельзя захватить последний замок: для этого нужны $$$14$$$ воинов, но вы можете собрать не более $$$13$$$ до захвата последнего замка.