You all probably know what Guitar
Basically you just strum a bunch of notes (~N~ of them) at the right time to gain points - nothing interesting for a program.
But one interesting aspect is Star Power: the ability to double your points for a certain time.
After you play a certain sequence of notes correctly, your Star Power
meter will fill up by one notch.
You can activate Star Power at anytime.
When activated, the meter starts to drain and each "notch" will give you some time ~(T)~ where every note is worth double.
For our purposes the meter is infinite, and you don't need a minimum number of notches to activate it.
Also, once you activate Star Power, you cannot deactivate it.
If you happen to accumulate more Star Power while it is active, it will just add onto your meter (and it will get used up).
Here's the interesting part: sometimes it's better to save Star Power for later (i.e. save it for an insane section)
So, you've mastered the game to the point where you can play all the
Now you'd like to maximize your score (with the help of a program), so that you can set a high score!
~N \le 10\,000~ (the number of notes), ~T \le 1\,000\,000\,000~ (the duration of
a single Star Power-up)
~N~ pairs of integers ~(a, b)~ – ~(a \le 10\,000, b \le 1\,000\,000\,000)~ indicating that a note with point value ~a~ comes at time ~b~.
There are no chords; all notes will have unique times.
~M \le N~ (the number of Star Power sequences)
~M~ pairs of positive integers ~(a, b)~ – ~(a \le b \le N)~ indicating that playing the ~a~-th to ~b~-th notes correctly gives you Star Power.
As an example, if there are ~3~ notes that come at times ~(2,5,3)~, the ~2~-nd note in the sequence is at time ~3~.
(Obviously, the notes come in order of time)
None of these sequences will overlap.
All numbers in the input are positive integers.
Your maximum possible score.
Sample Input 1
10 4 2 1 100 2 600 3 600 4 1 6 2 7 2 8 2 9 10 10 1 5 1 3 4
Sample Output 1
(Note that the times may not be in order.)
Save your Star Power, then activate it right when you play the note at time ~6~.
Star Power ends just when you play the note at time ~10~ (which still counts!)
This way you get ~2 + 100 + 600 \times 2 + 1 + 2 \times (1 + 2 \times 3 + 10)~ points.
Sample Input 2
5 1 1 100 1 200 1 300 1 600 1 700 3 1 1 2 2 4 4
Sample Output 2
Activate Star Power at time ~200~ (no matter what you do, you can only
double one of notes ~1~, ~2~ and ~3~)
Later, activate it at time ~700~ to gain another double pointer.