← 返回题目列表

Codeforces · 469/B

B. 在线聊天

中文机器翻译题面 查看原题

小X和小Z是好朋友。他们总是在网上聊天。但两人都有时间表。

小Z有固定的日程。他总是在a1和b1之间、a2和b2之间、...、ap和bp之间(包括所有边界)之间的任何时刻在线。不过小X的作息时间比较奇怪,要看他起床的时间。如果他在时间 0 起床,则他将在 c1 和 d1 之间、c2 和 d2 之间、...、cq 和 dq 之间(包括所有边界)之间的任何时刻在线。但如果他在时间 t 起床,这些片段就会移动 t。它们变成 [ci + t, di + t](对于所有 i)。

如果某个时刻,小X和小Z同时在线,他们就可以愉快地在线聊天了。您知道小 X 可以在 l 和 r(包括边界)之间的整数时刻起床。另外你知道小X想在适合和小Z聊天的时刻起床(他们的日程安排中必须至少有一个共同的时刻)。段 [l, r] 中有多少个整数时刻适合该情况?

输入

第一行包含四个空格分隔的整数 p、q、l、r(1 ≤ p、q ≤ 50;0 ≤ l ≤ r ≤ 1000)。

接下来的 p 行包含两个空格分隔的整数 ai, bi (0 ≤ ai < bi ≤ 1000)。接下来的 q 行中的每一行包含两个以空格分隔的整数 cj, dj (0 ≤ cj < dj ≤ 1000)。

对于所有有效的 i 和 j,保证 bi < ai + 1 且 dj < cj + 1。

输出

输出一个整数——[l,r]段中适合在线对话的时刻的数量。

示例

输入 #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