求助一道站外题

题目描述

小 A 所在的国家一年一共有 $N$ 天，今年的第一天是星期一。

这个国家对未成年人实行了防沉迷系统，未成年人只能在周五、周六、周日和法定节假日的20:00-21:00玩游戏。

目前已经知道国家今年的放假安排，有 $A$ 个放假安排和 $B$ 个加班安排。

对于第 $i$ 个放假安排：

• 从第 $L_i$ 天到第 $R_i$ 天放假。

对于第 $i$ 个加班安排：

• 从第 $L'_i$ 天到第 $R'_i$ 天加班。

所有放假安排中的日子以及前一天可以玩游戏，但是加班的日子不能玩游戏。

请求出小 A 今年可以玩多少天游戏。

输入格式

输入形如这样的格式：

N
A B
L1 R1
L2 R2
...
LA RA
L'1 R'1
L'2 R'2
...
L'B R'B

输出格式

一个整数，表示小 A 今年可以玩多少天游戏。

样例一

input

12
0 0

output

4

comment

小 A 在第 $5,6,7,12$ 天可以玩游戏。

样例二

input

12
2 1
1 6
10 10
7 7

output

8

comment

第 $1,2,3,4,5,6,10$ 天放假，第 $7$ 天加班。

小 A 在第 $1, 2, 3, 4, 5, 6, 10, 12$ 天可以玩游戏。

数据范围

$1 \leq N \leq 10^9$, $0 \leq A,B \leq 2 \times 10^5$.

$1 \leq L_i \leq R_i \leq N$, $1 \leq L'_i \leq R'_i \leq N$.

注意 $L_i = 1$ 时的情况。

保证只有周末会加班。

• 对于 $10\%$ 的数据，保证 $A = 0$, $B = 0$.
• 另有 $20\%$ 的数据，保证 $A \leq 2000$, $R_i-L_i \leq 2000$, $B = 0$.
• 另有 $20\%$ 的数据，保证 $A,B \leq 2000$, $R_i-L_i \leq 2000$, $R'_i - L'_i \leq 2000$.
• 另有 $20\%$ 的数据，保证 $N \leq 10^6$。
• 另有 $30\%$ 的数据，无其他限制。

---

时间限制：$2\texttt{s}$

空间限制：$1024\texttt{MB}$