Problem Statement

Snuke runs a bakery. He is planning for the next $N$ days. Let us call these days Day $1,2,\cdots,N$.

At the moment, the bakery hires nobody. There are $M$ bakers that Snuke can hire, numbered $1$ to $M$.

$C_i$ yen must be paid to hire Baker $i$. If Baker $i$ is hired, they will work on Day $L_i, L_i+1, \cdots, R_i$, baking one loaf of bread each day.

For each $j$ ($1 \leq j \leq N$), there is a limit $A_j$ to the number of loaves of bread that can be sold on Day $j$. If $x_j$ loaves of bread are baked on Day $j$, $\min(x_j, A_j)$ loaves will be sold on that day.

Each loaf of bread sold will yield a profit of $D$ yen.

Snuke wants to choose the set of bakers to hire to maximize the final profit: $($The total number of loaves sold$) \times D - ($The total cost of hiring bakers$)$. Find the maximum possible value of this.

Constraints

• $1 \leq N \leq 2000$
• $1 \leq M \leq 2000$
• $1 \leq D \leq 10^9$
• $1 \leq A_j \leq M$
• $1 \leq L_i \leq R_i \leq N$
• $1 \leq C_i \leq 10^9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M D
A_1 A_2 \cdots A_N
L_1 R_1 C_1
L_2 R_2 C_2
\vdots
L_M R_M C_M

Output

Print the answer.