分数: 800 点
问题陈述
Snuke 经营一家面包店。 他正在计划下一步 N 天。 让我们把这些日子称为“日” 1,2,\cdots,N.
目前,面包店不雇用任何人。 有 M Snuke 可以雇佣的面包师,编号 1 to M.
C_i 雇用贝克必须支付日元 i。 如果贝克 i 已被雇用,他们将在 Day 工作 L_i, L_i+1, \cdots, R_i,每天烤一条面包。
对于每个 j (1 \leq j \leq N),有限制 A_j 当天可以出售的面包数量 j。如果 x_j 面包在这一天烤制 j, \min(x_j, A_j) 面包将在当天出售。
每售出一条面包将产生利润 D 日元。
Snuke 想要选择一组聘请的面包师以最大化最终利润: (售出的面包总数) \times D - (雇用面包师的总成本)。 求这个值的最大可能值。
约束
- 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
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
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
输出
打印答案。
样本输入 1
7 4 3 1 1 1 1 1 1 1 1 2 3 2 4 5 4 6 3 6 7 1
示例输出 1
11
Snuke 应该雇佣 Baker 1, 3, 4。 在这种情况下,雇用面包师的总成本是 7,以及当天烘烤的面包数量 分别为 1, 2, \cdots, N 将是 1,1,0,1,1,2,1。总共有 6 面包将被出售,最终利润为 6 \times 3-7=11.
示例输入 2
3 1 5 1 1 1 2 2 10
示例输出 2
0
最好不要聘请面包师。
示例输入 3
10 10 42 6 5 1 5 2 4 2 7 10 9 3 4 4 3 7 136 9 9 14 2 7 152 3 3 33 2 4 100 3 3 38 1 10 28 3 5 66 8 8 15
示例输出 3
543