*Throw the balls into the open mouths!*

*Making a shot when the mouth is glowing is worth extra!*

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 units of time (from time to time
). 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 units of
time.

#### Input Specification

The first line of the input contains three integers, , , and 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 lines each contain a tuple (,
), which means that the **upper** Cheep Chomp opens its
mouth from time to time (inclusive). If , that means its
mouth is open normally (so each goal is 1 point). When , it means
that the mouth is open with rainbow glowing (so each goal is 3 points).
These time intervals do not overlap with each other, and are sorted
by time.

The next lines each also contain a tuple
(, ), which means that the **lower**
Cheep Chomp opens its mouth from time to time (inclusive).
Similarly, means normal and means rainbow. These 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 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, , , .

For 100% test cases, , , .

There are 16 test cases, 5 points each.

## Comments