Вы играете в стратегическую компьютерную игру (да, у нас закончились идеи для легенд задач). В этой игре вы управляете огромной армией, и ваша задача — захватить \(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\) будут уже недоступны.
Если в какой-то момент вам не хватает воинов для захвата следующего замка, вы проигрываете. Ваша цель — максимизировать суммарную важность всех охраняемых замков после захвата последнего замка (обратите внимание, что вы можете нанимать воинов в последнем замке после его захвата, оставлять в нем охрану и пользоваться порталами — суммарная важность всех охраняемых замков будет подсчитана после всех ваших действий).
Можете ли вы разработать оптимальную стратегию захвата замков и оставления охраны?
Выходные данные
Если невозможно захватить все замки ни при каких обстоятельствах, выведите одно целое число \(-1\).
Иначе выведите одно целое число — максимальную суммарную важность всех охраняемых замков в конце игры.
Примечание
Лучшая стратегия в первом примере — следующая:
- захватить первый замок;
- нанять солдат в первом замке, теперь у вас \(11\) солдат;
- захватить второй замок;
- захватить третий замок;
- нанять солдат в третьем замке, теперь у вас \(13\) солдат;
- захватить четвертый замок;
- оставить одного воина в четвертом замке, теперь у вас \(12\) солдат.
Эта стратегия (и некоторые другие) дает в результате суммарную важность охраняемых замков, равную \(5\).
Лучшая стратегия во втором примере — следующая:
- захватить первый замок;
- нанять солдат в первом замке, теперь у вас \(11\) солдат;
- захватить второй замок;
- захватить третий замок;
- нанять солдат в третьем замке, теперь у вас \(13\) солдат;
- захватить четвертый замок;
- оставить одного воина в четвертом замке, теперь у вас \(12\) солдат;
- отправить одного воина в первый замок через третий портал, теперь у вас \(11\) солдат.
Эта стратегия (и некоторые другие) дает в результате суммарную важность охраняемых замков, равную \(22\).
В третьем примере нельзя захватить последний замок: для этого нужны \(14\) воинов, но вы можете собрать не более \(13\) до захвата последнего замка.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3 7
7 4 17
3 0 8
11 2 0
13 3 5
3 1
2 1
4 3
|
5
|
|
2
|
4 3 7
7 4 17
3 0 8
11 2 0
13 3 5
3 1
2 1
4 1
|
22
|
|
3
|
4 3 7
7 4 17
3 0 8
11 2 0
14 3 5
3 1
2 1
4 3
|
-1
|