F: カードゲーム

問題

カードを使ったゲームを $Q$ 回行います。 カードには $1 \cdots N$ の数が書かれており、各数が書かれたカードはゲームを行うのに十分な枚数があります。 $i$ 回目のゲームでは、はじめに手札として 2 枚のカードが配られます。 それぞれのカードに書かれている数字は $x_i$ と $y_i$ です。 カードはルールに従って交換することができます。 $j$ 番目 $(1 \le j \le M)$ のルールでは、カード $a_j$ を手数料 $c_j$ 円で別のカード $b_j$ に交換することができます。 各ルールは何回でも用いることができます。また、手数料が足りなくて交換できない場合はありません。 最後に、手札のカードの数字を $R$ で割ったあまりが等しい時、報酬として $z_i$ 円受け取ります。 異なる場合報酬は $0$ 円です。

$Q$ 回ゲームを終えた時に増やすことのできるお金の最大値を求めてください。

制約

• $1 \le N \le 10^5$
• $0 \le M \le \min(2 \times 10^5, N\times(N-1))$
• $2 \le R \le 10$
• $1 \le Q \le 10^5$
• $1 \le a_j, b_j \le N$
• $a_j \neq b_j$
• $0 \le c_j \le 10^5$
• $1 \le x_i, y_i \le N$
• $0 \le z_i \le 10^5$

入力

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

$N \ M \ R \ Q$
$a_1 \ b_1 \ c_1$
$\vdots$
$a_M \ b_M \ c_M$
$x_1 \ y_1 \ z_1$
$\vdots$
$x_Q \ y_Q \ z_Q$

出力

ゲームを $Q$ 回行ったときに増やすことのできるお金の最大値を 1 行で出力してください。また、末尾に改行も出力してください。

サンプル

入力例 1

4 4 2 2
1 2 1
2 3 1
3 4 5
4 1 7
1 4 5
2 4 3

出力例 1

7

1 回目のゲームではカード 1 を手数料 1 でカード 2 に交換すると手札のカードを 2 で割った時のあまりがどちらも 0 となり、得られる報酬は 5 となります。 2 回目のゲームではすでに 2 で割ったときのあまりがどちらも 0 であり、得られる報酬は 3 となります。 2 回のゲームの結果、増やせるお金は $5-1+3=7$ です。

入力例 2

4 4 2 1
1 2 1
2 3 1
3 4 5
4 1 7
3 4 2

出力例 2

0

カードの交換での手数料が報酬よりも多いので、交換を行わないのが最適です。

Note

Commentary

 

---