{"raw_statement":[{"iden":"problem statement","content":"Snuke runs a bakery. He is planning for the next $N$ days. Let us call these days Day $1,2,\\cdots,N$.\nAt the moment, the bakery hires nobody. There are $M$ bakers that Snuke can hire, numbered $1$ to $M$.\n$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.\nFor 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.\nEach loaf of bread sold will yield a profit of $D$ yen.\nSnuke 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."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 2000$\n*   $1 \\leq M \\leq 2000$\n*   $1 \\leq D \\leq 10^9$\n*   $1 \\leq A_j \\leq M$\n*   $1 \\leq L_i \\leq R_i \\leq N$\n*   $1 \\leq C_i \\leq 10^9$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$ $D$\n$A_1$ $A_2$ $\\cdots$ $A_N$\n$L_1$ $R_1$ $C_1$\n$L_2$ $R_2$ $C_2$\n$\\vdots$\n$L_M$ $R_M$ $C_M$"},{"iden":"sample input 1","content":"7 4 3\n1 1 1 1 1 1 1\n1 2 3\n2 4 5\n4 6 3\n6 7 1"},{"iden":"sample output 1","content":"11\n\nSnuke should hire Baker $1, 3, 4$. In this case, the total cost to hire bakers is $7$, and the number of loaves baked on Day $1, 2, \\cdots, N$ will be $1,1,0,1,1,2,1$, respectively. A total of $6$ loaves will be sold, for a final profit of $6 \\times 3-7=11$."},{"iden":"sample input 2","content":"3 1 5\n1 1 1\n2 2 10"},{"iden":"sample output 2","content":"0\n\nIt is optimal to hire no baker."},{"iden":"sample input 3","content":"10 10 42\n6 5 1 5 2 4 2 7 10 9\n3 4 4\n3 7 136\n9 9 14\n2 7 152\n3 3 33\n2 4 100\n3 3 38\n1 10 28\n3 5 66\n8 8 15"},{"iden":"sample output 3","content":"543"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}