## 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]

**Languages Allowed:**

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

## Comments (Search)

braxton111on Jul 28, 2013 - 7:49:49 pm UTC wrong outputwhat does this output mean i keep getting it but i dont have a clue what it is or how to fix it??

Alexon Jul 28, 2013 - 8:22:07 pm UTC Re: wrong outputIn your case, it is a TLE:

javicon Sep 28, 2009 - 4:03:30 pm UTC GH:WT Mobilejavicon Sep 28, 2009 - 4:03:52 pm UTC Re: GH:WT Mobilehansonw1on Sep 28, 2009 - 11:34:54 pm UTC Re: GH:WT Mobilejavicon Sep 28, 2009 - 4:01:32 pm UTC This problem is awesomedr3won Sep 27, 2009 - 7:22:04 pm UTC lol