AT_abc421_g.[ABC421G] Increase to make it Increasing

给定长度为 $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$ 进行如下操作任意次（可能为 $0$ 次）：

• 选择一个整数 $i$，其中 $1 \leq i \leq M$，然后将每个 $A_{L_i}, A_{L_i+1},\dots, A_{R_i}$ 的值加 $1$。

请判断是否可以通过若干次操作使得 $A$ 非递减。如果可以，请输出所需操作次数的最小值；如果不可能，则输出 $-1$。

输入按以下格式给出：

$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

例如，按以下顺序执行四次操作，可以使 $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

无论如何操作，也无法使 $A$ 成为非递减序列。

样例解释 3

$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$
• 所有输入数据均为整数。

由 ChatGPT 5 翻译