G. Медуза и шифрование
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Медуза любит играть в игру «Inscryption», которая проводится на направленном ациклическом графе с $$$n$$$ вершинами и $$$m$$$ ребрами. Все ребра $$$a \to b$$$ удовлетворяют условию $$$a < b$$$.

Вам необходимо переместиться из вершины $$$1$$$ в вершину $$$n$$$ по направленным ребрам, а затем сразиться с финальным боссом.

При этом Вы будете собирать карточки и предметы.

Каждая карта имеет два атрибута: HP и урон. Если HP карты составляет $$$a$$$, а урон — $$$b$$$, то сила карты равна $$$a \times b$$$.

Каждый предмет имеет только один атрибут: силу.

Попадание в некоторые вершины (не равные $$$1$$$ и $$$n$$$) может вызывать неторые события. События бывают следующих типов:

  1. Вы получите карту с $$$a$$$ HP и $$$b$$$ уроном.
  2. Если у вас есть хотя бы одна карта, выберите одну из ваших карт и увеличьте ее HP на $$$x$$$.
  3. Если у вас есть хотя бы одна карта, выберите одну из ваших карт и увеличьте ее урон на $$$y$$$.
  4. Вы получите предмет с силой $$$w$$$.

Когда вы доберетесь до вершины $$$n$$$, вы можете выбрать не более одной из ваших карт и умножить ее урон на $$$10^9$$$.

Финальный босс очень силен, поэтому вы хотите максимизировать сумму сил всех ваших карт и предметов. Найдите максимально возможную сумму сил всех ваших карт и предметов, если вы играете оптимально.

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

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \leq n \leq 200$$$, $$$n - 1\leq m \leq \min(\frac{n(n-1)}2, 2000)$$$) — количество вершин и количество ребер.

В следующих $$$n$$$ строках $$$i$$$-я $$$(1 \leq i \leq n)$$$ строка описывает специальное событие, которое сработает на вершине $$$i$$$:

  • 0 — никаких особых событий.
  • 1 a b ($$$1 \leq a, b \leq 200$$$) — вы получите карту с $$$a$$$ HP и $$$b$$$ урона.
  • 2 x ($$$1 \leq x \leq 200$$$) — если у вас есть хотя бы одна карта, выберите одну из своих карт и увеличьте её HP на $$$x$$$.
  • 3 y ($$$1 \leq y \leq 200$$$) — если у вас есть хотя бы одна карта, выберите одну из своих карт и увеличьте ее урон на $$$y$$$.
  • 4 w ($$$1 \leq w \leq 10^6$$$) — вы получите реквизит с силой $$$w$$$.

В следующих $$$m$$$ строках каждая строка содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1 \leq u < v \leq n$$$), представляющих собой направленное ребро из вершины $$$u$$$ в вершину $$$v$$$.

Гарантируется, что каждое ребро $$$(u,v)$$$ встречается не более одного раза.

Гарантируется, что в вершине $$$1$$$ и вершине $$$n$$$ нет особых событий.

Гарантируется, что для всех $$$i$$$ существует путь из вершины $$$1$$$ в вершину $$$n$$$, проходящий через вершину $$$i$$$.

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

Выведите одно целое число — максимальную сумму мощностей всех ваших карт и предметов.

Примеры
Входные данные
6 8
0
1 2 10
1 6 6
2 8
3 10
0
1 2
1 3
2 4
2 5
3 4
3 5
4 6
5 6
Выходные данные
100000000000
Входные данные
4 3
0
4 1000000
4 1000000
0
1 2
2 3
3 4
Выходные данные
2000000
Входные данные
16 15
0
1 1 10
1 10 1
2 4
3 4
1 20 20
2 30
3 20
1 1 100
2 9
1 1 200
2 9
3 10
1 190 100
2 10
0
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
Выходные данные
20000000005600
Входные данные
9 9
0
1 1 200
3 200
3 200
3 200
3 200
1 200 200
3 200
0
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
1 9
Выходные данные
80000000001000
Входные данные
9 8
0
1 20 200
3 200
3 200
2 5
1 100 200
3 200
3 200
0
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
Выходные данные
60000000015000
Входные данные
16 34
0
0
0
2 6
3 1
4 27
4 40
3 9
0
2 6
1 8 1
0
2 2
1 10 7
2 9
0
2 4
3 10
2 11
2 7
13 15
3 15
2 3
6 14
4 12
10 12
9 10
7 8
4 13
11 12
4 6
11 16
14 15
2 5
5 15
9 13
8 14
1 3
2 15
12 16
7 10
4 5
1 2
4 11
4 9
4 16
3 6
6 8
7 11
15 16
Выходные данные
133000000040
Примечание

В первом примере можно играть в игру в следующем порядке:

  • переместиться из вершины $$$1$$$ в вершину $$$2$$$, получить карту с HP $$$2$$$ и уроном $$$10$$$.
  • переместиться из вершины $$$2$$$ в вершину $$$4$$$, выбрать карту, полученную из вершины $$$2$$$, и увеличить её HP на $$$8$$$.
  • переместиться из вершины $$$4$$$ в вершину $$$6$$$, выбрать карту, полученную из вершины $$$2$$$, и умножить её урон на $$$10^9$$$.

В итоге мы получим карту с $$$(2+8)=10$$$ HP и $$$10 \times 10^9=10^{10}$$$ урона, ее сила равна $$$10 \times 10^{10}=10^{11}$$$. Поскольку у нас есть только карта, полученная из вершины $$$2$$$, то сумма мощностей всех карт и предметов равна $$$10^{11}$$$.