Problem I
Museum Visit
Every day is different in the Groninger Museum. Some days are nice, peaceful and quiet, and you can spend all day looking at the beautiful paintings, sculptures, and other artworks. Other days are busier, when weekends or public holidays fill the museum with hasty visitors, increased prices and screaming children. This discomfort varies a lot: some busy days are better because of extra studentenkorting (student discount) and some of the quiet days get worse because of earthquake risks.
The museum also regularly hosts special limited-time exhibitions, such as those on the local football club FC Groningen, the Martinitoren, or the eierbal (a local delicacy). These exhibitions can be very irregular: some last for weeks, some last only a day, and there may be multiple exhibitions on the same day.
As a proud Grunneger, you want to visit each exhibition at least once. Luckily, you are subscribed to the newsletter so you know the start and end days of all the exhibitions in advance. Additionally, since you are a regular visitor at the museum, you have observed all the crowd and earthquake patterns, so you know exactly how much discomfort you will receive when you visit the museum on any specific day.
On which days should you visit the museum in order to minimize your total discomfort while still seeing all exhibitions that are planned in the foreseeable future? As an example, consider the first sample case. To minimize your total discomfort, you should visit the first two exhibitions on the second day and the last exhibition on the fourth or fifth day.
Input
The input consists of:
-
One line with two integers $n$ and $m$ ($1\leq n,m\leq 2\cdot 10^5$), the number of days in the foreseeable future and the number of exhibitions planned in those days.
-
One line with $n$ integers $c$ ($1\leq c\leq 10^9$), describing for each day the discomfort you will receive when you visit the museum.
-
$m$ lines, each with two integers $s$ and $e$ ($1\leq s\leq e\leq n$), describing the start and end day of an exhibition. The start and end days are inclusive: the exhibition can be visited on day $s$, day $e$, and any day in between.
Output
Output the minimum total discomfort you will receive when visiting all exhibitions of the Groninger Museum.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 3 1 1 3 1 1 1 3 2 3 3 5 |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
6 3 1 2 4 4 2 1 1 4 2 5 3 6 |
3 |
| Sample Input 3 | Sample Output 3 |
|---|---|
11 2 3 1 4 1 5 9 2 6 5 3 5 5 10 1 1 |
5 |
