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, higher prices and screaming children. The discomfort varies a lot: some busy days are better because of the extra studentenkorting (student discount), and some quiet days get worse because of earthquake risks.

The museum also 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 are irregular. Some last for weeks, some last only a day, and several may open on the same day.

As a proud Grunneger, you want to visit each exhibition at least once. You subscribed to the newsletter, so you know the start and end days of all exhibitions in advance. You are also a regular visitor, so you know exactly how much discomfort you will receive on any given day.

On which days should you visit the museum to minimize your total discomfort while still seeing every exhibition planned in the foreseeable future?

For example, in the first sample, the best plan is to visit the first two exhibitions on the second day and the last exhibition on the fourth or fifth day.

The input consists of:

• One line with two integers $n$ and $m$ ($1\leq n,m\leq 2\cdot10^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$), where $c_i$ is the discomfort you receive when you visit on day $i$.
• $m$ lines, each with two integers $s$ and $e$ ($1\leq s\leq e\leq n$), the start and end day of an exhibition. Both days are inclusive, so the exhibition can be visited on day $s$, on day $e$, and on any day in between.

Output the minimum total discomfort you receive while visiting all exhibitions.