Two Captains

The Black Pearl has two captains: Captain Jack Sparrow and Barbossa. The ship has exactly $n$ cannons arranged in a row. During a battle, both captains give commands to their crews at the same time once per minute. The commands are:

• send $l$ $r$: sends their crew to fire the cannons numbered from $l$ to $r$ inclusive
• back $l$ $r$: recalls all of their crew from the cannons numbered from $l$ to $r$ inclusive. Cannons in this range that have no crew loyal to this captain are left unchanged
• rum: brings one more bottle of rum

Each command is executed instantly, and then the battle continues for one minute until the next command. If at any moment crew members loyal to different captains are on the same cannon, they fight and kill each other. No captain wants this, so they asked you to help them fix the problem.

Before the battle, each captain made a plan of actions. Jack Sparrow's plan has $m_1$ commands, and Barbossa's plan has $m_2$ commands. At the start of minute $i$, each captain gives his crew the $i$-th command from his plan, if the plan has at least $i$ commands. You must fix the plans so that all crew members survive. The only change you can make is to insert several rum commands at any positions in the plans. Captains do not like changing their plans, so the total number of rum commands you add to both plans must be minimal.

The first line contains $n$, the number of cannons ($1 \le n \le 10^9$).

The second line contains $m_1$, the number of commands in Jack Sparrow's plan ($1 \le m_1 \le 3000$). The next $m_1$ lines list the commands in that plan, in the format described above. For every command using $l$ and $r$, $1 \le l \le r \le n$ holds. The last command in the plan is back 1 $n$.

The next line contains $m_2$, the number of commands in Barbossa's plan ($1 \le m_2 \le 3000$). The next $m_2$ lines list the commands in that plan, with the same constraints. The last command in the plan is back 1 $n$.

Print one line with the minimum number of additional commands.