{"problem":{"name":"Bakery","description":{"content":"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 ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc137_e"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc137_e","tags":[],"sample_group":[["7 4 3\n1 1 1 1 1 1 1\n1 2 3\n2 4 5\n4 6 3\n6 7 1","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$."],["3 1 5\n1 1 1\n2 2 10","0\n\nIt is optimal to hire no baker."],["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","543"]],"created_at":"2026-03-03 11:01:13"}}