Problem Statement

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

無事に渡されたチョコレートによる幸福度の合計値として考えられる最大値はいくらか。

Input

入力は以下の形式で標準入力から与えられる。

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$ 点が与えられる。

Output

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