問題文

$N$ 人の買い手が居るオークションで $M$ 個の商品が出品されています． このオークションでは，

• 各商品は高々 $1$ 人の買い手に売ることができ，
• 各買い手は高々 $1$ 個の商品を買うことができます．

売り値を細かく決めるのが億劫だった D.D. 君は，各商品 $j$ に対して以下の手順を実行しました．

• はじめに，商品 $j$ を買う意思がある買い手全員に挙手をさせる．
• $k = 0, 1, \dots, K$ に対し，商品 $j$ が $2^k$ 円で売られた場合に買う意思のある買い手には挙手を続けさせ，そうでない買い手には手を下ろさせる．

「買い手 $X$ が商品 $Y$ に対して $k = Z$ 時点まで挙手を続けた」という情報が $L$ 個与えられます． 面倒くさがり屋な D.D. 君の代わりに，どの商品をどの買い手にいくらで売るかを上手く決めて，総売り上げを最大化してあげてください． ただし，与えられる情報から買い手の買う意思が明確であるような売り方のみが可能であるとします．

入力

$N\ \ M\ \ K\ \ L$
$X_1\ \ Y_1\ \ Z_1$
$X_2\ \ Y_2\ \ Z_2$
    $\vdots$
$X_L\ \ Y_L\ \ Z_L$

• $1 \le N, M \le 25000$
• $0 \le K \le 30$
• $0 \le L \le 25000$
• $1 \le X_i \le N \ \ (1 \le i \le L)$
• $1 \le Y_i \le M \ \ (1 \le i \le L)$
• $0 \le Z_i \le K \ \ (1 \le i \le L)$
• $X_i \neq X_j$ または $Y_i \neq Y_j \ \ (1 \le i < j \le L)$
• 入力は全て整数である．
• 買い手には $1, 2, \dots, N$ の番号が付いている．
• 商品には $1, 2, \dots, M$ の番号が付いている．
• 各 $(X_i, Y_i, Z_i)$ は「買い手 $X_i$ に商品 $Y_i$ を $2^{Z_i}$ 円（以下）で売ることができる」ことを表す．

出力

各商品の買い手と売り値の組合せ（売らない場合を含む）を決めたときにあり得る総売り上げ（円）の最大値を出力してください．

サンプル

2 2 2 4
1 1 2
1 2 2
2 1 1
2 2 0

6

3 3 4 3
1 1 4
2 1 3
1 2 2

16

5 7 30 16
3 1 29
1 3 29
5 6 28
4 7 30
1 1 30
1 7 29
3 6 30
5 3 28
2 1 29
4 3 30
4 2 28
4 1 29
1 5 30
2 4 29
3 3 29
3 4 29

4026531840