← 返回题目
题库练习 Jellyfish and Inscryption
← 上一题 下一题 →

A16214 | Jellyfish and Inscryption

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

Jellyfish loves playing a game called "Inscryption" which is played on a directed acyclic graph with $n$ vertices and $m$ edges. All edges $a \to b$ satisfy $a < b$ .

You need to move from vertex $1$ to vertex $n$ along the directed edges, and then fight with the final boss.

You will collect cards and props in the process.

Each card has two attributes: HP and damage. If a card's HP is $a$ and its damage is $b$ , then the power of the card is $a \times b$ .

Each prop has only one attribute: power.

In addition to vertex $1$ and vertex $n$ , there are some vertices that trigger special events. The special events are:

1. You will get a card with $a$ HP, and $b$ damage.
2. If you have at least one card, choose one of your cards and increase its HP by $x$ .
3. If you have at least one card, choose one of your cards and increase its damage by $y$ .
4. You will get a prop with $w$ power.

When you get to vertex $n$ , you can choose at most one of your cards and multiply its damage by $10^9$ .

The final boss is very strong, so you want to maximize the sum of the power of all your cards and props. Find the maximum possible sum of power of all your cards and props if you play the game optimally.

输入格式

The first line contains two integers $n$ and $m$ ( $2 \leq n \leq 200$ , $n - 1\leq m \leq \min(\frac{n(n-1)}2, 2000)$ ) — the number of the vertices and the number of the edges.

In the following $n$ lines, the $i$ -th $(1 \leq i \leq n)$ line describes the special event that will trigger on vertex $i$ :

- 0 — no special events.
- 1 a b ( $1 \leq a, b \leq 200$ ) — you will get a card with $a$ HP, and $b$ damage.
- 2 x ( $1 \leq x \leq 200$ ) — if you have at least one card, choose one of your cards and increase its HP by $x$ .
- 3 y ( $1 \leq y \leq 200$ ) — if you have at least one card, choose one of your cards and increase its damage by $y$ .
- 4 w ( $1 \leq w \leq 10^6$ ) — you will get a prop with $w$ power.

In the following $m$ lines, each line contains two integers $u$ and $v$ ( $1 \leq u < v \leq n$ ) representing a directed edge from vertex $u$ to vertex $v$ .

It is guaranteed that every edge $(u,v)$ appears at most once.

It is guaranteed that there are no special events on vertex $1$ and vertex $n$ .

It is guaranteed that for all $i$ , there exists a path from vertex $1$ to vertex $n$ that passes through vertex $i$ .

输出格式

Output a single integer — the maximum sum of the power of all your cards and props.

输入输出样例

输入 #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
输出 #1
100000000000
输入 #2
4 3
0
4 1000000
4 1000000
0
1 2
2 3
3 4
输出 #2
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
输出 #3
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
输出 #4
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
输出 #5
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
输出 #6
133000000040
C++ 编辑器
输入
输出