Chat Online

题意翻译

给你$p$个$[a,b]$的区间和$q$个$[c,d]$的区间，现给出区间$[l,r]$，问你区间$[l,r]$内有多少个整数$t$满足区间$[c+t,d+t]$与区间$[a,b]$有交集。

题目描述

Little X and Little Z are good friends. They always chat online. But both of them have schedules. Little Z has fixed schedule. He always online at any moment of time between $ a_{1} $ and $ b_{1} $ , between $ a_{2} $ and $ b_{2} $ , ..., between $ a_{p} $ and $ b_{p} $ (all borders inclusive). But the schedule of Little X is quite strange, it depends on the time when he gets up. If he gets up at time $ 0 $ , he will be online at any moment of time between $ c_{1} $ and $ d_{1} $ , between $ c_{2} $ and $ d_{2} $ , ..., between $ c_{q} $ and $ d_{q} $ (all borders inclusive). But if he gets up at time $ t $ , these segments will be shifted by $ t $ . They become $ [c_{i}+t,d_{i}+t] $ (for all $ i $ ). If at a moment of time, both Little X and Little Z are online simultaneosly, they can chat online happily. You know that Little X can get up at an integer moment of time between $ l $ and $ r $ (both borders inclusive). Also you know that Little X wants to get up at the moment of time, that is suitable for chatting with Little Z (they must have at least one common moment of time in schedules). How many integer moments of time from the segment $ [l,r] $ suit for that?

输入输出格式

输入格式

The first line contains four space-separated integers $ p,q,l,r $ ( $ 1<=p,q<=50; 0<=l<=r<=1000 $ ). Each of the next $ p $ lines contains two space-separated integers $ a_{i},b_{i} $ ( $ 0<=a_{i}&lt;b_{i}<=1000 $ ). Each of the next $ q $ lines contains two space-separated integers $ c_{j},d_{j} $ ( $ 0<=c_{j}&lt;d_{j}<=1000 $ ). It's guaranteed that $ b_{i}&lt;a_{i+1} $ and $ d_{j}&lt;c_{j+1} $ for all valid $ i $ and $ j $ .

输出格式

Output a single integer — the number of moments of time from the segment $ [l,r] $ which suit for online conversation.

输入输出样例

输入样例 #1

1 1 0 4
2 3
0 1

输出样例 #1

3

输入样例 #2

2 3 0 20
15 17
23 26
1 4
7 11
15 17

输出样例 #2

20