問題一覧 > 通常問題

No.119 The Travel Tour Problem

レベル : / AI推定難易度 : 2500 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 95
作問者 : nmnmnmnmnmnmnm
お気に入りにしたユーザー ProblemId : 7 / 自分の提出
問題文最終更新日: 2026-06-27 14:35:10
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 73 (順位表) の他の問題:

Problem Statement

There are N countries.
The countries are numbered from the 0th to the (N-1)th.
A-kun has chosen, from the N countries, the countries he wants to travel to.
A-kun always travels to the countries in increasing order of their numbers.

When he went to a travel agency, it turned out that each country has one tour.
However, while some of the agency's tours are good,
others are rather unpleasant because they reduce his freedom.
A satisfaction value is set according to whether he goes on the tour or not.

Also, according to the travel agency staff, if you go on a certain tour, you must also join the tour of another country:
there seem to be several conditions of this kind.
For example,

・If you go on the tour of the x-th country, you must go on the tour of the y-th country (x<y)

is such a condition.
This condition applies if he goes to both the x-th country and the y-th country.
A-kun doesn't really understand why, but he has decided to accept the conditions.
Satisfaction is added up over the entire trip.
A-kun wants to obtain as much satisfaction as possible.
Answer the maximum satisfaction.

In other words, as long as each condition is satisfied,
・Do not go to the x-th country.
・Go to the x-th country, but do not join the tour.
・Go to the x-th country and also join the tour.
he can choose any one of these.

Input

$N$
$B_0$ $C_0$
$\vdots$
$B_{n-1}$ $C_{n-1}$
$M$
$D_0$ $E_0$
$\vdots$
$D_{m-1}$ $E_{m-1}$

$N$ is a positive integer. $1 \le N \le 40$.
Then, information about the tours of the $N$ countries is given, one per line.
$B_i$ is the satisfaction if he goes on the tour of the $i$-th country.
$C_i$ is the satisfaction if he does not go on the tour of the $i$-th country.
$B_i$ and $C_i$ are both integers at least $0$. $0 \le B_i,C_i \le 100$.
Note that $B_i > C_i$ does not necessarily hold.
$M$ is an integer at least $0$. $0 \le M \le \frac{N\times(N-1)}{2}$.
Then, information about the $M$ tour participation conditions is given, one per line.
The $j$-th condition is: if he travels to both the $D_j$-th country and the $E_j$-th country,
then if he goes on the tour of the $D_j$-th country, he must also go on the tour of the $E_j$-th country.
$D_j$ and $E_j$ are integers between $0$ and $N-1$, inclusive. $0 \le D_j,E_j \le N-1$.
Here, $D_j < E_j$ always holds.
If $i \neq j $, then $(D_i,E_i) \neq (D_j,E_J)$.

Output

Output the maximum satisfaction on one line.
Don't forget the newline.

Sample

Sample 1
Input
2
20 10
30 50
1
0 1
Output
60

There are 2 countries.
First, he decides to travel to the 0th and 1st countries.
The satisfaction information for each country's tour is as follows.
Going on the tour of the 0th country gives a satisfaction of 20.
Not going on the tour of the 0th country gives a satisfaction of 10.
Going on the tour of the 1st country gives a satisfaction of 30.
Not going on the tour of the 1st country gives a satisfaction of 50.
The tours must always be visited in increasing order of country number.
The travel agency gives 1 condition regarding tours.
If he joins the tour of the 0th country, he must also join the tour of the 1st country.

If there were no condition from the travel agency,
it would be best to join the tour of the 0th country and not join the tour of the 1st country.
In that case the satisfaction would be maximized at 20+50=70.
In reality, however, joining the 0th tour requires joining the 1st tour as well.
In this case, the satisfaction is 20+30=50.
In the end, it is best to go on neither the 0th tour nor the 1st tour.
The satisfaction is 10+50=60.
Therefore, the maximum satisfaction is 60.

Sample 2
Input
2
20 30
40 20
1
0 1
Output
70

First, he decides to travel to the 0th and 1st countries.
Next, he decides not to go on the tour of the 0th country but to go on the tour of the 1st country.
In this case, the maximum satisfaction is 30+40=70.
The condition says that when he goes on the 0th tour, he must go on the 1st tour.
However, conversely, going on the 1st tour does not mean he must go on the 0th tour.

Sample 3
Input
3
10 1
1 1
1 10
2
0 1
1 2
Output
20

First, he decides to travel to the 0th and 2nd countries.
He goes on the tour of the 0th country.
He does not go on the tour of the 2nd country.
This gives the maximum satisfaction of 10+10=20.
If he also decided to go to the 1st country,
then going on the tour of the 0th country would require going on the tour of the 1st country as well.
That would in turn require going on the tour of the 2nd country too,
so the satisfaction would be as low as 10+1+1=12.
Note that going to all the countries is not necessarily advantageous.

Sample 4
Input
30
86 10
18 59
84 75
93 0
42 20
67 28
77 5
62 54
82 76
30 62
11 60
7 18
72 69
91 76
28 16
66 37
46 21
20 2
59 22
23 99
9 99
22 1
22 100
61 24
11 97
14 95
81 65
34 90
19 53
89 49
35
0 3
0 11
0 15
0 21
1 14
1 18
1 20
1 23
2 11
2 13
2 19
3 17
4 10
4 17
6 9
6 17
6 20
9 16
9 28
11 17
11 28
12 15
14 26
15 22
15 24
16 23
16 25
17 27
19 24
19 25
22 24
23 26
23 29
24 27
25 28
Output
1828

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。