分数: 600 点
问题陈述
给你一个长度-N 整数序列 A=(A_1,A_2,\ldots,A_N)。 还给你 M 整数对 (L_1, R_1), (L_2, R_2), \dots, (L_M, R_M)\ (1\leq L_i\leq R_i\leq N).
您可以按顺序执行以下操作 A 任意次数(可能为零):
- 选择一个整数 i 与 1 \leq i \leq M,并添加 1 到每个 A_{L_i}, A_{L_i+1},\dots, A_{R_i}.
判断是否可以使 A 非递减,如果可能,求所需的最少操作数。
约束
- 1\leq N \leq 300
- 1\leq M \leq 300
- 1\leq A_i \leq 300
- 1\leq L_i\leq R_i\leq N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M A_1 A_2 \dots A_N L_1 R_1 L_2 R_2 \vdots L_M R_M
输出
如果可以的话 A 非递减,打印所需的最少操作次数。如果不可能,则打印 -1.
示例输入 1
4 3 4 2 3 2 2 2 2 3 4 4
示例输出 1
4
例如,通过执行如下操作四次,可以使 A 非递减:
- 选择 i=1 并执行操作。 A 变为 (4,3,3,2).
- 选择 i=3 并执行操作。 A 变为 (4,3,3,3).
- 选择 i=3 并执行操作。 A 变为 (4,3,3,4).
- 选择 i=2 并执行操作。 A 变为 (4,4,4,4).
相反,不可能使 A 三次或更少操作时非递减。 因此,打印 4.
示例输入 2
3 2 3 1 2 2 2 1 2
示例输出 2
-1
无论你如何操作,都不可能使 A 非减少。
示例输入 3
4 4 1 1 2 3 1 1 2 2 3 3 4 4
示例输出 3
0
A 已经是非递减的,因此不需要进行任何操作。
示例输入 4
8 12 35 29 36 88 58 15 25 99 5 5 1 6 3 8 8 8 4 8 7 7 5 7 3 3 2 6 1 6 6 7 5 7
示例输出 4
79