P14103 [ZJCPC 2017] Let's Chat

ACM (ACMers' Chatting Messenger) is a famous instant messaging software developed by Marjar Technology Company. To attract more users, Edward, the boss of Marjar Company, has recently added a new feature to the software. The new feature can be described as follows: If two users, $A$ and $B$, have been sending messages to $\textbf{each other}$ on the last $m$ $\textbf{consecutive}$ days, the "friendship point" between them will be increased by $1$ point. More formally, if user $A$ sent messages to user $B$ on each day between the $(i-m+1)$-th day and the $i$-th day (both inclusive), and user $B$ also sent messages to user $A$ on each day between the $(i-m+1)$-th day and the $i$-th day (also both inclusive), the "friendship point" between $A$ and $B$ will be increased by $1$ at the end of the $i$-th day. Given the chatting logs of two users $A$ and $B$ during $n$ consecutive days, what's the number of the friendship points between them at the end of the $n$-th day (given that the initial friendship point between them is $0$)?

There are multiple test cases. The first line of input contains an integer $T$ ($1 \le T \le 10$), indicating the number of test cases. For each test case: The first line contains four integers $n$ ($1 \le n \le 10^9$), $m$ ($1 \le m \le n$), $x$ and $y$ ($1 \le x, y \le 100$). The meanings of $n$ and $m$ are described above, while $x$ indicates the number of chatting logs about the messages sent by $A$ to $B$, and $y$ indicates the number of chatting logs about the messages sent by $B$ to $A$. For the following $x$ lines, the $i$-th line contains two integers $l_{a,i}$ and $r_{a,i}$ ($1 \le l_{a,i} \le r_{a,i} \le n$), indicating that $A$ sent messages to $B$ on each day between the $l_{a,i}$-th day and the $r_{a,i}$-th day (both inclusive). For the following $y$ lines, the $i$-th line contains two integers $l_{b,i}$ and $r_{b,i}$ ($1 \le l_{b,i} \le r_{b,i} \le n$), indicating that $B$ sent messages to $A$ on each day between the $l_{b,i}$-th day and the $r_{b,i}$-th day (both inclusive). It is guaranteed that for all $1 \le i < x$, $r_{a,i} + 1 < l_{a,i+1}$ and for all $1 \le i < y$, $r_{b,i} + 1 < l_{b,i+1}$.

For each test case, output one line containing one integer, indicating the number of friendship points between $A$ and $B$ at the end of the $n$-th day.

For the first test case, user $A$ and user $B$ send messages to each other on the $1$-st, $2$-nd, $3$-rd, $5$-th, $6$-th, $7$-th, $8$-th and $10$-th day. As $m=3$, the friendship points between them will be increased by $1$ at the end of the $3$-rd, $7$-th and $8$-th day. So the answer is $3$.