Медуза любит играть в игру «Inscryption», которая проводится на направленном ациклическом графе с \(n\) вершинами и \(m\) ребрами. Все ребра \(a \to b\) удовлетворяют условию \(a < b\).
Вам необходимо переместиться из вершины \(1\) в вершину \(n\) по направленным ребрам, а затем сразиться с финальным боссом.
При этом Вы будете собирать карточки и предметы.
Каждая карта имеет два атрибута: HP и урон. Если HP карты составляет \(a\), а урон — \(b\), то сила карты равна \(a \times b\).
Каждый предмет имеет только один атрибут: силу.
Попадание в некоторые вершины (не равные \(1\) и \(n\)) может вызывать неторые события. События бывают следующих типов:
- Вы получите карту с \(a\) HP и \(b\) уроном.
- Если у вас есть хотя бы одна карта, выберите одну из ваших карт и увеличьте ее HP на \(x\).
- Если у вас есть хотя бы одна карта, выберите одну из ваших карт и увеличьте ее урон на \(y\).
- Вы получите предмет с силой \(w\).
Когда вы доберетесь до вершины \(n\), вы можете выбрать не более одной из ваших карт и умножить ее урон на \(10^9\).
Финальный босс очень силен, поэтому вы хотите максимизировать сумму сил всех ваших карт и предметов. Найдите максимально возможную сумму сил всех ваших карт и предметов, если вы играете оптимально.
Выходные данные
Выведите одно целое число — максимальную сумму мощностей всех ваших карт и предметов.
Примечание
В первом примере можно играть в игру в следующем порядке:
- переместиться из вершины \(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}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
2
|
4 3
0
4 1000000
4 1000000
0
1 2
2 3
3 4
|
2000000
|
|
3
|
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
|
|
4
|
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
|
|
5
|
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
|
|
6
|
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
|