Minimum Cost Base Station Placement

China Mobile Shenzhen Branch was registered in \(1999\). Four years later, the Guangdong Collegiate Programming Contest was held for the first time. Both have witnessed the prosperity and development of the computer industry in Guangdong.

During the construction of a communication line spanning \(n\) kilometers from west to east, engineers must decide where to build base stations. The cost to build a base station at kilometer \(i\) is \(a_i\). In addition, there are \(m\) requirements. The \(i\)-th requirement is given as a pair of integers \(l_i\) and \(r_i\) (with \(1 \le l_i \le r_i \le n\)), meaning that there must be at least one base station built between kilometers \(l_i\) and \(r_i\) (inclusive).

Your task as the chief engineer is to choose the locations for the base stations (possibly building as many as needed) so that all requirements are satisfied, while minimizing the total cost of construction.

Input Format Example:
The first line contains two integers \(n\) and \(m\).
The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\), where \(a_i\) denotes the cost of building a base station at kilometer \(i\).
Each of the following \(m\) lines contains two integers \(l_i\) and \(r_i\), representing a requirement.

Note: All formulas are formatted in \(\LaTeX\).

inputFormat

The first line contains two integers \(n\) and \(m\).
The second line contains \(n\) space‐separated integers \(a_1, a_2, \ldots, a_n\), the cost to build a base station at kilometer \(i\).
Then \(m\) lines follow, each containing two integers \(l_i\) and \(r_i\) (with \(1 \leq l_i \leq r_i \leq n\)), representing that there must be at least one base station between kilometers \(l_i\) and \(r_i\) (inclusive).

outputFormat

Output the minimum total cost to fulfill all the requirements.

sample

5 2
1 2 3 4 5
1 3
3 5

3