AT_abc421_g [ABC421G] Increase to make it Increasing

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.

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 $

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

### Sample Explanation 1 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 Explanation 2 No matter how you perform operations, it is impossible to make $ A $ non-decreasing. ### Sample Explanation 3 $ A $ is already non-decreasing, so no operations are needed. ### 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.