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 翻译