Hero Power

Rhythm games are having a good October, with two big titles shipping in the same month. Bj0rn is getting ready to top the scoreboards of the newer one, and he needs help working out the maximum score for every new song. The new game has something called Hero Power, and Bj0rn is betting that it is the same thing as the Star Power these games have always had.

Scoring works like this. The player advances along a note chart and scores one point for every note he hits. Bj0rn will settle for nothing less than perfection, so every note gets hit.

Star Power, simply called SP, is the twist. Every now and then a streak of star shaped notes appears on the chart, and such a streak is an SP phrase. While between the first and the last note of an SP phrase, the player can charge the SP meter, which stores the amount of time spent charging. Charging can start at the exact moment of the first note and continue all the way to the last note. Charging can be paused at any time, and the stored charge does not have to be used right away, so charge from several phrases can add up.

When the SP meter holds a positive amount of time, the player is free to activate Star Power at any point in the song, even at the exact moment of a note. From that moment the meter starts draining until it is completely empty. A meter holding $\pi + \sqrt[4]{7}$ milliseconds takes $\pi + \sqrt[4]{7}$ milliseconds to drain. During an activation every note is worth two points as long as the meter is not empty. A note hit at the exact moment of activation is already worth two points, and a note hit at the exact moment the meter becomes empty is worth one point.

Activating has a downside. If an SP activation overlaps an SP phrase and the meter is positive somewhere in the overlap, that phrase degrades back to plain notes. If the first note of a phrase is hit at the exact moment the meter drains to 0, the phrase does not degrade. Activating in the middle of a phrase is allowed, but the rest of that phrase still suffers from the overlap and disappears, so no more Star Power can be charged from it.

Find the best strategy for Bj0rn and report how many points he gets.

The first line has two integers $n$ and $p$ ($1 \le n \le 50\,000$, $0 \le p \le 100$), the number of notes and the number of SP phrases. The second line has $n$ strictly increasing integers $t_i$ ($0 \le t_i \le 50\,000\,000$), the positions of the notes in milliseconds. Each of the next $p$ lines has two integers $s_i$ and $e_i$ ($0 \le s_i < e_i \le 50\,000\,000$), the start and the end of the $i$-th SP phrase.

A note exists at the start position and at the end position of every SP phrase. SP phrases never overlap and are given in ascending order.

Print the maximum score as a single integer.