Guitar Hero^TM

You all probably know what Guitar Hero is.
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 notes perfectly.
Now you'd like to maximize your score (with the help of a program), so that you can set a high score!

Input

N ≤ 10,000 (the number of notes), T ≤ 1,000,000,000 (the duration of a single Star Power-up)
N pairs of integers (a,b) - (a ≤ 10,000, b ≤ 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 ≤ N (the number of Star Power sequences)
M pairs of positive integers (a,b) - (a ≤ b ≤ 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 2nd 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.

Output

Your maximum possible score.

Sample Input

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

1337

(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*2 + 1 + 2*(1+2*3+10) points.

Sample Input

5 1
1 100
1 200
1 300
1 600
1 700
3
1 1
2 2
4 4

Sample Output

7

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.

All Submissions
Best Solutions

Point Value: 25 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Nov 02, 2008
Author: hansonw1

Problem Types: [Show] [Hide]

• Dynamic Programming

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)