← 返回题目列表

AtCoder · arc137_e

E. 面包店

中文机器翻译题面 查看原题

分数: 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