G - Increase to make it Increasing Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 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 に対して、以下の操作を好きな回数（0 回でも良い）行うことができます。

  • 1 以上 M 以下の整数 i を選び、A_{L_i}, A_{L_i+1},\dots, A_{R_i} にそれぞれ 1 を足す。

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

例えば以下のように操作を 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) になる。

逆に、3 回以下の操作で 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 は元から広義単調増加なので、1 回も操作をする必要はありません。

入力例 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

Score : 600 points

Problem Statement

You are given a length-N integer sequence A=(A_1,A_2,\ldots,A_N). You are also given M pairs of integers (L_1, R_1), (L_2, R_2), \dots, (L_M, R_M)\ (1\leq L_i\leq R_i\leq N).

You can perform the following operation on sequence A any number of times (possibly zero):

  • Choose an integer i with 1 \leq i \leq M, and add 1 to each of A_{L_i}, A_{L_i+1},\dots, A_{R_i}.

Determine whether it is possible to make A non-decreasing, and if possible, find the minimum number of operations required.

Constraints

  • 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
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
A_1 A_2 \dots A_N
L_1 R_1
L_2 R_2
\vdots
L_M R_M

Output

If it is possible to make A non-decreasing, print the minimum number of operations required. If it is impossible, print -1.

Sample Input 1

4 3
4 2 3 2
2 2
2 3
4 4

Sample Output 1

4

For example, by performing operations four times as follows, you can make A non-decreasing:

  • Choose i=1 and perform the operation. A becomes (4,3,3,2).
  • Choose i=3 and perform the operation. A becomes (4,3,3,3).
  • Choose i=3 and perform the operation. A becomes (4,3,3,4).
  • Choose i=2 and perform the operation. A becomes (4,4,4,4).

Conversely, it is impossible to make A non-decreasing with three or fewer operations. Thus, print 4.

Sample Input 2

3 2
3 1 2
2 2
1 2

Sample Output 2

-1

No matter how you perform operations, it is impossible to make A non-decreasing.

Sample Input 3

4 4
1 1 2 3
1 1
2 2
3 3
4 4

Sample Output 3

0

A is already non-decreasing, so no operations are needed.

Sample Input 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

Sample Output 4

79