Монокарп играет в компьютерную игру «Гоблины и гномы». В этой игре он управляет подземным городом гномов, защищающимся от орд гоблинов.
Подземный город состоит из $$$n$$$ залов и $$$m$$$ односторонних туннелей, соединяющих некоторые пары залов. Структура туннелей такова, что, выйдя из какого-то зала, нельзя вернуться в него обратно по тоннелям.
На город готовится $$$k$$$ атак гоблинов, в $$$i$$$-й атаке город атакуют $$$i$$$ гоблинов. Цель Монокарпа — выдержать все $$$k$$$ атак.
$$$i$$$-я атака происходит следующим образом: сначала $$$i$$$ гоблинов появляются в каких-то залах города и грабят их, при этом в каждом зале появляется не более одного гоблина. После этого гоблины начинают перемещаться из зала в зал по туннелям, попутно грабя каждый зал на своем пути.
Гоблины очень жадные и хитрые, а поэтому планируют выбирать свои стартовые залы и пути так, что никакие два гоблина не пройдут через один и тот же зал. При этом, среди всех возможных планов атаки они выбирают такой, что позволяет в сумме разграбить максимальное количество залов. После того как гоблины разграбили максимальное количество залов, они покидают город.
Если в результате атаки все залы оказались разграблены — Монокарп проигрывает. Иначе гномам удается восстановить город. Если какой-то зал оказался разграблен в ходе атаки, то в ходе следующих атак он все равно представляет интерес для гоблинов (гномы успевают восстановить его).
Перед каждой атакой у Монокарпа есть время для подготовки. Монокарп может готовиться бесконечно долго (он сам решает, когда вызвать каждую атаку), но чем дольше он готовится к атаке, тем меньше очков он получает. Если Монокарп готовился к $$$i$$$-й атаке $$$t_i$$$ минут, то после нее он получает $$$\max(0, x_i - t_i \cdot y_i)$$$ очков (естественно, если он не проигрывает).
Во время подготовки к атаке Монокарп может блокировать туннели. За одну минуту он может заблокировать либо все туннели, ведущие в некоторый зал, либо все туннели, ведущие из некоторого зала. Если Монокарп заблокировал какой-то туннель во время подготовки к атаке, то этот туннель остается заблокированным и во время следующих атак.
Помогите Монокарпу выдержать все $$$k$$$ атак гоблинов и набрать максимальное количество очков!
В первой строке задано три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$2 \le n \le 50$$$; $$$0 \le m \le \frac{n(n - 1)}{2}$$$; $$$1 \le k \le n - 1$$$) — количество залов в городе, количество туннелей, и количество атак гоблинов, соответственно.
Далее следуют $$$m$$$ строк, описывающих туннели. В $$$i$$$-й из этих строк заданы два числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \ne v_i$$$), соответствующих туннелю из зала $$$u_i$$$ в зал $$$v_i$$$. Структура туннелей такова, что, выйдя из какого-то зала, гоблин не может вернуться в него обратно по тоннелям. Между каждой парой залов существует не более одного туннеля.
Далее следуют $$$k$$$ строк, описывающих, как Монокарп получает очки за атаки. В $$$i$$$-й строке заданы два числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i \le 10^9$$$; $$$1 \le y_i \le 10^9$$$). Если Монокарп готовился к $$$i$$$-й атаке $$$t_i$$$ минут, то после нее он получает $$$\max(0, x_i - t_i \cdot y_i)$$$ очков.
Выведите оптимальную последовательность действий Монокарпа в следующем формате:
В первой строке выведите целое число $$$a$$$ ($$$k \le a \le 2n + k$$$) — количество действий, которые совершает Монокарп. Во второй строке выведите сами эти действия в том порядке, в котором Монокарп их выполняет. $$$i$$$-е действие описывается целым числом $$$b_i$$$ ($$$-n \le b_i \le n$$$) в следующем формате:
Нельзя повторять одно и то же действие по блокировке $$$b_i$$$ несколько раз. Каждый раз, когда Монокарп вызывает очередную атаку гоблинов, он должен выдержать ее (у гоблинов не должно быть возможности разграбить все залы города). Монокарп должен выдержать ровно $$$k$$$ атак и получить максимально возможное количество очков.
Если существует несколько оптимальных последовательностей действий — выведите любую из них.
5 4 4 1 2 2 3 4 3 5 3 100 1 200 5 10 10 100 1
6 -2 -3 0 0 0 0
5 4 4 1 2 2 3 4 3 5 3 100 100 200 5 10 10 100 1
6 0 -3 0 0 1 0
5 10 1 1 2 1 3 1 4 1 5 5 2 5 3 5 4 4 2 4 3 2 3 100 100
6 1 2 3 4 5 0
В первом примере Монокарп сначала блокирует все туннели, ведущие в зал $$$2$$$, а потом — все туннели, ведущие в зал $$$3$$$, после чего вызывает все атаки. Он готовился к атаке $$$1$$$ две минуты, поэтому он получает за нее $$$98$$$ очков. К остальным атакам он не готовился, поэтому получает максимально возможные очки за них ($$$200$$$, $$$10$$$ и $$$100$$$). Суммарно он набирает $$$408$$$ очков.
Во втором примере Монокарп сразу вызывает первую атаку и получает за нее $$$100$$$ очков. Перед второй атакой он блокирует все туннели, ведущие в зал $$$3$$$. Это означает, что он готовится к ней одну минуту и получает $$$195$$$ очков за нее. К третьей атаке Монокарп не готовится и получает $$$10$$$ очков. Перед четвертой атакой он блокирует туннели, ведущие из зала $$$1$$$, это означает, что он готовится к атаке одну минуту и получает за нее $$$99$$$ очков. Суммарно он набирает $$$404$$$ очка.
В третьем примере Монокарпу не важно, сделает он одно действие или несколько перед единственной атакой, так как он в любом случае не получит за нее очков. А потому блокирует все туннели в городе, потратив на это целых $$$5$$$ минут и переживает атаку, не получив за нее очков.
Название |
---|