Problem Statement

$N$ slimes are lined up in a row from left to right.

The color of the $i$-th slime from the left is $C_i$. (Colors are treated as integers.)

You may perform the following operation between $0$ and $N$ times, inclusive.

• Eat the slime at the leftmost position. The eaten slime disappears, and you gain $X$ points.

In addition to the score obtained from the above operations, you can gain additional score based on the final arrangement of slimes after all operations have been performed.

There are $M$ scoring items: if the color of the $A_j$-th slime from the left is $B_j$, you gain $Y_j$ points. (If the $A_j$-th slime from the left does not exist, you cannot gain the score.)

Find the maximum score you can obtain.

Constraints

• $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$
• All input values are integers.

Input

The input is given from standard input in the following format.

$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$

Output

Output the answer to the problem on a single line.

Sample

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