Feeding Friendsy is a 4-player minigame in Super Mario Party, and you can view how the game is actually played here.

The rules are rather simple. As shown below, there are two Cheep Chomp (the two big mouthed fish) mechs, which will open their mouths during certain time intervals. Each player will throw balls into the mouths of the Cheep Chomps and if they go into the open mouths, they get points. When the open mouth appears normal like the top Cheep Chomp, each goal is worth one point. If the mouth is glowing with an arcing rainbow like the bottom Cheep Chomp, each goal is worth three points. Every player can throw at most one ball at one unit of time, either to the upper or the lower Cheep Chomp.

Mario always did better than any of the other players in this game. Now he wants to make sure that he can beat anybody. In order to improve, he recorded the gameplay and watched it to find out the best strategy. The duration of each game is ~T~ units of time (from time ~0~ to time ~T-1~). Given all the time periods that each Cheep Chomp has its mouth open, and the information about whether they are normal or rainbow, we want to know the maximum points one can earn within ~T~ units of time.

Input Specification

The first line of the input contains three integers, ~T~, ~n~, and ~m~ that represent the duration of the game, the number of time intervals that the upper Cheep Chomp opens its mouth, and the number of time intervals that the lower Cheep Chomp opens its mouth respectively.

The next ~n~ lines each contain a tuple ~a, b, c~ (~0 \le a \le b \le T-1~, ~c \in \{0,1\}~), which means that the upper Cheep Chomp opens its mouth from time ~a~ to time ~b~ (inclusive). If ~c=0~, that means its mouth is open normally (so each goal is 1 point). When ~c=1~, it means that the mouth is open with rainbow glowing (so each goal is 3 points). These ~n~ time intervals do not overlap with each other, and are sorted by time.

The next ~m~ lines each also contain a tuple ~a, b, c~ (~0 \le a \le b \le T-1~, ~c \in \{0,1\}~), which means that the lower Cheep Chomp opens its mouth from time ~a~ to time ~b~ (inclusive). Similarly, ~c=0~ means normal and ~c=1~ means rainbow. These ~m~ time intervals do not overlap with each other, and are sorted by time.

Output Specification

The output only contains one integer, which is the highest possible score that Mario can get.

Sample Input 1

10 2 3
0 3 0
8 9 0
2 3 1
5 5 0
7 9 0

Sample Output 1

12

Sample Input 2

100 3 5
25 28 1
53 66 1
90 98 0
45 52 0
65 72 1
79 86 0
90 91 0
97 99 1

Sample Output 2

104

Sample Input 3

100 5 5
29 36 0
50 53 1
62 64 1
65 69 0
77 78 1
16 16 0
22 26 0
27 37 1
50 75 0
84 92 0

Sample Output 3

94

Explanation for Sample Outputs

Here's an example of one of the best solutions for the first sample input/output:

Time	0	1	2	3	4	5	6	7	8	9
Throw to upper?	x	x							x	x
Throw to lower?			x	x		x	x
Points Earned	1	1	3	3	0	1	0	1	1	1

x means that Mario threw the ball to that mouth at that time. So the maximum number of points he earns is ~1+1+3+3+1+1+1+1=12~ points.

Source of pictures and descriptions: https://www.mariowiki.com/Feeding_Friendsy. You can also find more details about the game from this site.

Scoring

For 25% of the test cases, ~0 \le T \le 10^4~, ~0 \le n \le 10^3~, ~0 \le m \le 10^3~.

For 100% test cases, ~0 \le T \le 10^8~, ~0 \le n \le 10^6~, ~0 \le m \le 10^6~.

There are 16 test cases, 5 points each.