AT_abc018_4 [ABC018D] バレンタインデー

[problemUrl]: https://atcoder.jp/contests/abc018/tasks/abc018_4 あるクラスには女子が $ N $ 人、男子が $ M $ 人いる。女子には $ 1 $ から $ N $ までの出席番号が、男子には $ 1 $ から $ M $ までの出席番号が割り当てられている。 幸運のキューピットはここから女子 $ P $ 人と男子 $ Q $ 人からなる、1 つの旅行グループを作る。 $ N $ 人の女子は合わせて $ R $ 個のチョコレートを持っており、チョコレートには $ 1 $ から $ R $ までの番号が付けられている。 チョコレート $ i\ (1\ ≦\ i\ ≦\ R) $ は出席番号が $ x_i $ である女子が持っており、旅行中に出席番号が $ y_i $ である男子に渡す予定である。そのため旅行グループに出席番号が $ x_i $ である女子と出席番号が $ y_i $ である男子が両方含まれていた場合に限り渡すことができる。無事にチョコレート $ i $ が渡された場合の幸福度は $ z_i $ である。 無事に渡されたチョコレートによる幸福度の合計値として考えられる最大値はいくらか。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ P $ $ Q $ $ R $ $ x_1 $ $ y_1 $ $ z_1 $ $ x_2 $ $ y_2 $ $ z_2 $ : $ x_R $ $ y_R $ $ z_R $ - $ 1 $ 行目には、$ 5 $ つの整数 $ N\ (1\ ≦\ N\ ≦\ 18) $, $ M\ (1\ ≦\ M\ ≦\ 18) $, $ P\ (1\ ≦\ P\ ≦\ N) $, $ Q\ (1\ ≦\ Q\ ≦\ M) $, $ R\ (1\ ≦\ R\ ≦\ N×M) $ が空白区切りで書かれている。これは、クラスに女子が $ N $ 人、男子が $ M $ 人おり、旅行グループは女子 $ P $ 人、男子 $ Q $ 人からなり、チョコレートが $ R $ 個あることを表す。 - $ 2 $ 行目から $ R $ 行には、チョコレートに関する情報が与えられる。$ R $ 行のうち $ i\ (1\ ≦\ i\ ≦\ R) $ 行目には、$ 3 $ つの整数 $ x_i\ (1\ ≦\ x_i\ ≦\ N) $, $ y_i\ (1\ ≦\ y_i\ ≦\ M) $, $ z_i\ (1\ ≦\ z_i\ ≦\ 10,000) $ が空白区切りで与えられる。これは、チョコレート $ i $ を出席番号が $ x_i $ である女子が持っており、旅行中に出席番号が $ y_i $ である男子に渡す予定であり、チョコレート $ i $ の幸福度が $ z_i $ であることを表す。 - $ 1\ ≦\ i\ ＜\ j\ ≦\ R $ である整数 $ i $,$ j $ に対して、$ x_i≠x_j $ または $ y_i≠y_j $ が成り立つ。

無事に渡されたチョコレートによる幸福度の合計値として考えられる最大値を $ 1 $ 行に出力せよ。(21:51 表現の変更)出力の末尾に改行を入れること。

### 部分点 この問題には部分点が設定されている。 - $ N\ ≦\ 8 $ かつ $ M\ ≦\ 8 $ を満たすデータセット $ 1 $ に正解した場合は、$ 30 $ 点が与えられる。 ### Sample Explanation 1 出席番号が $ 1 $, $ 2 $ の女子と出席番号が $ 2 $, $ 3 $, $ 4 $ の男子からなる旅行グループを考えます。 - チョコレート $ 1 $ は出席番号が $ 1 $ の男子が旅行に参加しないため、渡されません。 - チョコレート $ 2 $ は受け渡しする男女がともに旅行に参加するため、無事に渡されます。チョコレートの幸福度は $ 7 $ です。 - チョコレート $ 3 $ は受け渡しする男女がともに旅行に参加するため、無事に渡されます。チョコレートの幸福度は $ 15 $ です。 - チョコレート $ 4 $ は受け渡しする男女がともに旅行に参加するため、無事に渡されます。チョコレートの幸福度は $ 6 $ です。 - チョコレート $ 5 $ は受け渡しする男女がともに旅行に参加するため、無事に渡されます。チョコレートの幸福度は $ 3 $ です。 - チョコレート $ 6 $ は受け渡しする男女がともに旅行に参加するため、無事に渡されます。チョコレートの幸福度は $ 6 $ です。 - チョコレート $ 7 $ は出席番号が $ 3 $ の女子が旅行に参加しないため、渡されません。 幸福度の合計値は $ 7\ +\ 15\ +\ 6\ +\ 3\ +\ 6\ =\ 37 $ となり、これが最大値となります。