Everyone knows Adelaide is a cool place to live, and now it's your chance to prove it!

Today, ~n~ of your friends have flown in from out of state. You want to take everyone around the city, doing Adelaide's most fun activities!

Well, you'd like to at least. As CS students, your friends have wacky schedules, and are only available to join the tour during specific time windows. The activities you want to do also run over specific time windows, and you can't be two places at once!

Each activity has a fun value. If one of your friends fully participate in an activity with fun value ~F~, then your tour earns ~F~ credibility. If ~X~ friends participate in an activity with fun ~F~, then your tour earns ~X \times F~ credibility.

How can you select the activities you do, to maximise your credibility?

Input

The first line consists of an integer ~n~ ~(1 \leq n \leq 10^5)~, the number of friends you have.

The next ~n~ lines contain ~S_i~ and ~T_i~ ~(1 \leq S_i \leq T_i \leq 10^8)~., indicating that your ~i~th friend will join your tour at the start of time ~S_i~ and leave at the end of time ~T_i~.

The next line consists of an integer ~m~ ~(1 \leq m \leq 10^5)~, the number of activities you can do with your friends today.

The next ~m~ lines contain ~X_i~, ~Y_i~, and ~F_i~ ~(1 \leq X_i, Y_i, F_i \leq 10^8, X \leq Y)~, indicating that the ~i~th activity runs from the start of time ~X_i~ to the end of time ~Y_i~ and has ~F_i~ fun.

Output

Output the maximum "credibility" your tour can gain: the product of each activity's fun with the number of people who attend.

Clarifications

• Your friends join/leave your tour instantly.
• If a friend leaves halfway through an activity, your tour does not gain the credibility from that.
• If a friend joins the activity the exact time it starts, and leaves the exact time it ends, your tour will gain credibility.

Example

Input 1

3
1 5
3 6
5 7
5
1 2 3
1 5 4
3 4 3
4 7 5
6 7 2

Output 1

11

We pick activities ~1~ (1 2 3), ~3~ (3 4 3) and ~5~ (6 7 2) for our schedule.

• Friend ~1~ joins at ~t = 1~. You are now with ~1~ friend.
• Do activity ~1~ until ~t = 2~. This activity has ~3~ fun, so you get ~3~ credibility for each friend you are with. (~1 \times 3 = 3~ in total).
• Friend ~2~ joins at ~t = 3~. You are now with ~2~ friends.
• Do activity ~3~ until ~t = 4~. This activity has ~3~ fun, so you get ~3~ credibility for each friend you are with. (~2 \times 3 = 6~ in total).
• Friend ~1~ leaves at ~t = 5~. At the same time, friend ~3~ joins. You are still with ~2~ friends.
• Friend ~2~ leaves at ~t = 6~. You are now with ~1~ friend.
• Do activity ~5~ until ~t = 7~. This activity has ~2~ fun, so you get ~2~ credibility for each friend you are with. (~1 \times 2 = 2~ in total). Friend ~3~ also leaves at ~t = 7~.

Overall, your tour gains ~3 + 6 + 2 = 11~ credibility, which is the maximum possible.

Input 2

9
6 7
1 10
4 10
1 4
2 10
3 5
2 5
5 7
3 5
5
3 5 5
5 5 20
1 2 10
4 6 5
2 5 10

Output 2

160

We take activities ~2~ and ~3~. ~7~ friends attend activity ~2~, and ~2~ friends attend activity ~1~.

Input 3

3
1 5
1 4
2 5
6
1 1 1
2 2 1
3 3 1
4 4 1
5 5 1
1 5 10

Output 3

13

We take activities ~1~ through ~5~.