Reverse Direction Minimization

This is the simple version of the problem, worth 50 points. A ball is initially at point \(0\) on the number line and moves in the positive direction. Devices are placed at points \(1\) to \(n\), and when the ball passes point \(i\), it can change its moving direction (from positive to negative, or vice versa) at a cost of \(a_i\).

There are \(m\) conditions of the form "the ball must travel from point \(x_i\) to point \(y_i\) at least once", where \(x_i > y_i\). More formally, the ball's path must contain a segment of the form \[ \ldots \to x_i \to \ldots \to y_i \to \ldots \] for each condition \(i\).

Your task is to determine the minimum total cost required to satisfy all conditions. In the simple version the conditions are such that a single reversal is sufficient: if the ball reverses its direction at a point \(p\) such that \(p \geq \max_{1 \le i \le m} \{x_i\}\), and then travels leftwards sufficiently far to cover every required \(y_i\), all conditions are satisfied. In other words, the answer is the minimum \(a_p\) for \(p\) in the range \([L, n]\), where \(L = \max_{1 \le i \le m}\{x_i\}\).

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \leq n, m \leq 10^5)\) — the number of device positions and the number of conditions.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq 10^9)\) representing the cost at each point.

Then \(m\) lines follow. Each of these lines contains two integers \(x_i\) and \(y_i\) with the guarantee that \(1 \leq y_i < x_i \leq n\), representing a condition that the ball must travel from point \(x_i\) to point \(y_i\) (in that order) at least once.

outputFormat

Output a single integer: the minimum total cost required to satisfy all conditions.

sample

5 2
5 3 6 4 2
3 1
4 2

2