問題文

$N$ 体のスライムが左右一列に並んでいます。

左から $i$ 番目のスライムの色は $C_i$ です。（色は整数として扱います。）

あなたは、以下の操作を $0$ 回以上 $N$ 回以下行うことができます。

• 一番左の位置にあるスライムを食べる。このとき、食べたスライムはなくなり、あなたは $X$ 点を獲得する。

上記の操作で得たスコアに加え、操作を全て行った後の最終的なスライムの並びによって追加でスコアを得ることができます。

スコアを得ることのできる項目は $M$ 項目あり、左から $A_j$ 番目のスライムの色が $B_j$ である場合は $Y_j$ 点を獲得します。（左から $A_j$ 番目のスライムが存在しない場合はスコアを得ることができません。）

あなたの得ることのできるスコアの最大値を求めてください。

制約

• $1 \leq N, M \leq 2 \times 10^5$
• $0 \leq X \leq 100$
• $1 \leq C_i \leq 5$
• $1 \leq A_j \leq N$
• $1 \leq B_j \leq 5$
• $1 \leq Y_j \leq 100$
• 入力はすべて整数である。

入力

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

$N$ $M$ $X$  
$C_1$ $C_2$ ... $C_N$  
$A_1$ $B_1$ $Y_1$
$A_2$ $B_2$ $Y_2$
$\vdots$

$A_M$ $B_M$ $Y_M$

出力

問題の答えを一行に出力せよ。

サンプル

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

11

3 6 0
1 2 3
1 1 10
1 1 10
1 2 20
1 2 20
1 3 30
1 3 30

60