問題文

あるクラスには女子が $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