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 $ 回でも良い）行うことができます。 - $ 1 $ 以上 $ M $ 以下の整数 $ i $ を選び、 $ A_{L_i}, A_{L_i+1},\dots, A_{R_i} $ にそれぞれ $ 1 $ を足す。 $ A $ を広義単調増加にすることが可能かどうか判定し、可能ならば必要な操作回数の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_M $ $ R_M $

$ A $ を広義単調増加にすることが可能ならば必要な操作回数の最小値を、不可能ならば `-1` を出力せよ。

### Sample Explanation 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) $ になる。 逆に、 $ 3 $ 回以下の操作で $ A $ を広義単調増加にすることはできません。 よって $ 4 $ を出力します。 ### Sample Explanation 2 どのように操作をしても、 $ A $ を広義単調増加にすることはできません。 ### Sample Explanation 3 $ A $ は元から広義単調増加なので、 $ 1 $ 回も操作をする必要はありません。 ### 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 $ - 入力は全て整数