Background

Lianzi decides to study the physical properties of some objects to perfect her thesis. Due to the overwhelming amount of work, she invites you to help her complete a small experiment.

Problem Description

This is the easy version of the problem, where the conditions the ball needs to meet are different from the hard version. The full score for this problem is 50 points.

Lianzi has a ball that starts at point $0$ on a number line and moves in the positive direction. She has set up devices at points $1$ to $n$ on the number line. When the ball passes point $i$, she can spend a cost of $a_i$ to change its direction (from positive to negative, or vice versa).

Lianzi has $m$ conditions she needs to satisfy, where the $i$-th condition is that the ball must move from point $x_i$ to point $y_i$ at least once, with $x_i$ greater than $y_i$. More specifically, this condition requires the ball's movement path to be of the form $\ldots \to x_i \to \ldots \to y_i \to \ldots$.

Lianzi wants to know the minimum cost she needs to spend to satisfy all conditions.

Input Format

The first line contains two integers $n$ and $m$.

The second line contains $n$ positive integers describing the sequence $a$.

The next $m$ lines, the $i$-th line contains two positive integers representing $x_i$ and $y_i$.

Output Format

A single integer on one line, representing the minimum cost Lianzi needs to spend to satisfy all conditions.

Sample Input and Output

Sample Input #1

3 1
1 2 3
2 1

Sample Output #1

2

Sample Input #2

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

Sample Output #2

3

Notes

Sample Explanation

The figure shows the movement paths for the two samples. The costs for reversing direction at each point are shown above the number line, and the coordinates are below.

Sample #1

Lianzi reverses the ball's direction at point $2$ to exactly satisfy all conditions, with a total cost of $2$.

Sample #2

Lianzi reverses the ball's direction at point $3$ to exactly satisfy all conditions, with a total cost of $3$.

Data Range

This problem uses batched testing.

$$ \def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|c|}\hline \textbf{Subtask} & \textbf{\textsf{Points}} & \bm{n,m\le } & \bm{a_i\le} & \bm{x_i,y_i\le} & \textbf{\textsf{Special Conditions}}&\textbf{Subtask \textsf{Dependencies}}\cr\hline 1 & 10 & 10 & 100 & 10 & - &-\cr\hline 2 & 10 & 10^3 & 10^8 & 10^3 & -&1 \cr\hline 3 & 30 & 2\times 10^5 & 10^8 & 2\times 10^5 & -&1,2 \cr\hline \end{array} $$

For all data, the following holds: $1 \le n, m \le 2 \times 10^5$, $1 \le a_i \le 10^8$, $1 \le y_i < x_i \le n \le 2 \times 10^5$.

见题面 Input 部分

见题面 Output 部分