No.119 旅行のツアーの問題

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 26
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm

8 ProblemId : 7 / 出題時の順位表

問題文

N個の国があります。
国は0番目からN-1番目と数えます。
A君はN個の国から旅行に行きたい国を選びました。
A君は必ず小さい番目の国から順に旅行に出かけます。

旅行会社に行くと各国にはそれぞれ1つのツアーがあるようでした。
ただし、旅行会社のツアーというものは良いものもあれば、
返って自由度が減って嫌なものもあります。
ツアーに行くか行かないかで満足度が設定されています。

また、旅行会社の人が言うには、あるツアーに行ったら別の国のツアーにも参加しないといけない。
という条件がいくつかあるようでした。
例えば、

・x番目の国のツアーに行ったらy番目の国のツアーに行かなければならない(x<y)

というような条件です。
もし、x番目の国とy番目の国の両方に行くならこの条件が発生します。
A君は理由はよくわからないけど条件を呑むことにしました。
旅行の全行程を通して満足度は加算されていきます。
A君はより多くの満足度を得たいです。
最大の満足度を答えなさい。

すなわち、それぞれ条件をみたすのなら、
・x番目の国に行かない。
・x番目の国に行くけど、ツアーには参加しない。
・x番目の国に行き、ツアーにも参加する。
のどれかの選択ができるということである。

入力

$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$は正の整数。$1 \le N \le 40$。
以下、$N$個の国のツアーについて1行ごとに情報が与えられる。
$B_i$は$i$番目の国のツアーに行った場合の満足度。
$C_i$は$i$番目の国のツアーに行かなかった場合の満足度。
$B_i$、$C_i$は共に$0$以上の整数。$0 \le B_i,C_i \le 100$。
必ずしも$B_i > C_i$でないことに注意。
$M$は$0$以上の整数。$0 \le M \le \frac{N\times(N-1)}{2}$。
以下、$M$個のツアー参加の条件について1行ごとに情報が与えられる。
$j$番目の条件として、もし$D_j$番目の国にも$E_j$番目の国にも旅行するのであれば、
$D_j$番目の国のツアーに行ったら$E_j$番目の国のツアーにも行かなければならない。
$D_j$、$E_j$は$0$以上$N-1$以下の整数。$0 \le D_j,E_j \le N-1$。
このとき必ず$D_j < E_j$。
$i \neq j $であれば$(D_i,E_i) \neq (D_j,E_J)$

出力

最大の満足度を1行で答えよ。
改行を忘れずに。

サンプル

サンプル1
入力
2
20 10
30 50
1
0 1
出力
60

2つの国がある。
まず旅行に行く国を0番目と1番目の国に決める。
各国のツアーの満足度の情報は以下のようになる。
0番目の国のツアーに行くと満足度が20である。
0番目の国のツアーに行かないと満足度が10である。
1番目の国のツアーに行くと満足度が30である。
1番目の国のツアーに行かないと満足度が50である。
ツアーは必ず小さい番目の国から順に訪れる必要がある。
旅行会社から1つのツアーに関する条件がある。
0番目の国のツアーに参加したら1番目の国のツアーにも参加しなければならない。

もし旅行会社の条件が無ければ、
0番目の国のツアーに参加し1番目の国のツアーに参加しないのが最善である。
このとき満足度は20+50=70で最大になる。
ただし実際は0番目のツアーに参加すると1番目のツアーにも参加しなければならない。
この場合、満足度は20+30=50である。
結局、0番目のツアーにも行かず1番目のツアーにも行かないのがいちばん良い。
満足度は10+50=60である。
よって、最大の満足度は60となる。

サンプル2
入力
2
20 30
40 20
1
0 1
出力
70

まず旅行に行く国を0番目と1番目の国に決める。
次に、0番目の国のツアーに行かず1番目の国のツアーには行くと決める。
このとき最大の満足度は30+40=70である。
条件では0番目のツアーに行った時に1番目のツアーに行かなければならない。
ただし、逆に1番目のツアーに行くからといって0番目のツアーに行かないといけないわけではない。

サンプル3
入力
3
10 1
1 1
1 10
2
0 1
1 2
出力
20

まず旅行に行く国を0と2番目の国に決める。
0番目の国のツアーに行く。
2番目の国のツアーに行かない。
すると最大の満足度10+10=20が得られる。
もし1番目の国にも行くことを決めてしまうと、
0番目の国のツアーに行くときに1番目の国のツアーにも行かなければならない。
すると2番目の国のツアーにも行かなければならなくなってしまうので、
満足度は10+1+1=12と低くなってしまう。
必ずすべての国に行ったほうが有利でないことに注意。

サンプル4
入力
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
出力
1828
提出ページヘ