Shirotsume の誕生日を祝うためにケーキを作ります。材料として 個の果物が用意されています。 各 について、 個目の果物のおいしさは です。
あなたは、この 種類の果物の中から つまたは つを選んでケーキを作ります。選んだ果物が つの場合、ケーキのおいしさは選んだ果物のおいしさの和となります。選んだ果物が つの場合、その果物のおいしさと等しいおいしさのケーキができます。
しかし、 Shirotsume には 種類の嫌いな組合せがあり、 各 について、 個目の果物と 個目の果物が両方含まれているようなケーキは絶対に食べません。
Shirotsume が食べられるケーキであって、最もおいしさが大きいもののおいしさはいくらになるでしょうか?
N M A_1 A_2 ... A_N X_1 Y_1 X_2 Y_2 . . . X_M Y_M
おいしさの和としてあり得る最大値を一行に出力せよ。
4 2 3 1 4 1 1 3 2 3
5
個目と 個目の果物を組み合わせると、できるケーキのおいしさは ですが、Shirotsume の好き嫌いによりこのケーキを食べることはできません。
Shirotsume が食べられるケーキのうち、おいしさが最も大きいものは 個目の果物と 個目の果物が入ったおいしさ のケーキです。
3 3 1 10 100 1 2 1 3 2 3
100
つの果物の組合せ全てが嫌いな組合せです。よって、 つの果物しかケーキに入れることができません。答えは 個目の果物のみを含んだケーキのおいしさである です。