Problem E
Hero Power
Rhythm gaming seems to be having a bit of a renaissance this October, with both a new “Rock Band” and a “Guitar Hero” game coming out. Bj0rn is preparing to achieve top scores in “Guitar Hero Live”, but he needs your help in figuring out what the maximum score is for all the new songs. Apparently, the new game has something called Hero Power, but Bj0rn is betting that it really is the same thing as the “Star Power” that has always been in these games.
“Guitar Hero’s” scoring essentially works as follows: the player advances along a note chart and scores one point for each note he hits. Bj0rn will settle for nothing less than perfection; every note will be hit!
However, there’s an added twist: “Star Power!”—simply called SP. Every now and then, a streak of star-shaped notes appear on the note chart. These streaks are SP phrases. When between the first and last note of an SP phrase, the player has the ability to charge up a so-called SP meter, which stores the amount of time the player has spent charging it. You can start charging at the exact moment of the first note and all the way up till the last note. You can also pause charging at any time and you do not have to use the accumulated SP immediately after you stop charging, so it is possible to accumulate SP charge from multiple phrases.
When the SP meter contains a positive amount of seconds, at any point in the song—even at the exact moment of a note—the player is free to activate Star Power. From this moment, the SP meter starts draining until it is completely empty. For example, if it contains $\pi + {\root 4 \of {7}}$ seconds of SP, it will take $\pi + {\root 4 \of {7}}$ seconds to drain completely. During an activation, every note is worth two points as long as the SP meter is non-empty! In particular, if you start activating at the exact moment of a note, that note is already worth two points and if you hit a note during the last moment of activation, that note is only worth one point, because the SP meter has just become empty.
There is a downside to activating Star Power. If an SP activation overlaps with an SP phrase and the SP meter is positive at some point during the overlap, the SP phrase degrades back to plain notes. In particular, if you hit the first note of an SP phrase on the exact moment when the SP meter drains to $0$, the SP phrase is not degraded. It’s fine to activate mid-phrase, but the rest of the phrase still suffers from the overlap and disappears, so you can not charge more Star Power from that phrase.
Can you help Bj0rn find the best strategy and figure out how many points he can get?
Input
The first line of input consists of two integers $1 \leq n \leq 50\, 000$ and $0 \leq p \leq 100$, the number of notes and SP phrases respectively. The second line is a strictly increasing sequence of $n$ integers $0 \leq t_ i \leq 50\, 000\, 000$, the positions of all notes in milliseconds. Then follow $p$ lines containing two integers each, $0 \leq s_ i < e_ i \leq 50\, 000\, 000$, the positions of the start and end of the $i$’th Star Power phrase.
Notes are guaranteed to exist on the start and end positions of each SP phrase. SP phrases never overlap and are given in ascending order.
Output
The maximum score as a single integer.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 1 0 10 20 0 10 |
4 |
| Sample Input 2 | Sample Output 2 |
|---|---|
6 1 0 10 20 26 40 50 0 40 |
9 |
| Sample Input 3 | Sample Output 3 |
|---|---|
10 2 0 10 20 30 40 50 60 70 80 90 0 40 70 80 |
14 |
