← 返回题目列表

AtCoder · abc421_g

G. 增加使其增加

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

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