D - バレンタインデー Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

あるクラスには女子が 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 が成り立つ。

部分点

この問題には部分点が設定されている。

  • N ≦ 8 かつ M ≦ 8 を満たすデータセット 1 に正解した場合は、30 点が与えられる。

出力

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

入力例1

3 4 2 3 7
1 1 9
1 2 7
1 3 15
1 4 6
2 2 3
2 4 6
3 3 6

出力例1

37

出席番号が 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 となり、これが最大値となります。

入力例2

4 5 3 2 9
2 3 5
3 1 4
2 2 2
4 1 9
3 5 3
3 3 8
1 4 5
1 5 7
2 4 8

出力例2

26