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?


-----Input-----

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} < b_{i} ≤ 1000). Each of the next q lines contains two space-separated integers c_{j}, d_{j} (0 ≤ c_{j} < d_{j} ≤ 1000).

It's guaranteed that b_{i} < a_{i} + 1 and d_{j} < c_{j} + 1 for all valid i and j.


-----Output-----

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


-----Examples-----
Input
1 1 0 4
2 3
0 1

Output
3

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

Output
20

Difficulty: EASY
Tags: Implementation

Starter code:

Solutions:
from itertools import product
from math import ceil, gcd, sqrt
import string
from decimal import Decimal

def binary_table(string_with_all_characters, length_to_make):
	return [''.join(x) for x in product(string_with_all_characters, repeat=length_to_make)]

def all_possible_substrings(string):
	return [int(string[i:j]) for i in range(len(string)) for j in range(i + 1, len(string) + 1)]

def number_of_substrings(length):
	return int(length * (length + 1) / 2)
(num_of_z_lines, num_of_x_lines, l, r) = map(int, input().split())
z_lines = []
x_lines = []
for i in range(num_of_z_lines):
	(x, y) = map(int, input().split())
	z_lines.extend([x for x in range(x, y + 1)])
for i in range(num_of_x_lines):
	(x, y) = map(int, input().split())
	x_lines.extend([x for x in range(x, y + 1)])
num = 0
for i in range(l, r + 1):
	for j in x_lines:
		if j + i in z_lines:
			num += 1
			break
print(num)


def main():
	(p, q, l, r) = map(int, input().split())
	Z = set()
	X = []
	for _ in range(p):
		(ai, bi) = map(int, input().split())
		Z.update(range(ai, bi + 1))
	for _ in range(q):
		(ai, bi) = map(int, input().split())
		X.extend(range(ai, bi + 1))
	res = 0
	for i in range(l, r + 1):
		for j in X:
			if j + i in Z:
				res += 1
				break
	print(res)
main()


(p, q, l, r) = map(int, input().strip().split())
lz = [0 for __ in range(1001)]
lx = lz.copy()
res = 0
for i in range(p):
	(a, b) = map(int, input().split())
	for j in range(a, b + 1):
		lz[j] = 1
for i in range(q):
	(a, b) = map(int, input().split())
	for j in range(a, b + 1):
		lx[j] = 1
for i in range(l, r + 1):
	for ii in range(len(lz) + 1):
		if ii + i < 1001:
			if lx[ii] + lz[ii + i] == 2:
				res += 1
				break
print(res)


(p, q, l, r) = map(int, input().split())
x = [[int(j) for j in input().split()] for i in range(p)]
z = [[int(j) for j in input().split()] for i in range(q)]
moment = [0] * 1001
ans = 0
for i in x:
	for j in z:
		if i[1] - j[0] <= r or i[0] - j[1] <= r:
			for e in range(max(l, i[0] - j[1]), min(i[1] - j[0], r) + 1):
				if moment[e] == 0:
					ans += 1
					moment[e] = 1
print(ans)


def main():
	(p, q, l, r) = map(int, input().split())
	(ab, cd) = ([False] * (1001 - l), [False] * 1001)
	for _ in range(p):
		(a, b) = map(int, input().split())
		for i in range(1000 - b, 1001 - max(a, l)):
			ab[i] = True
	for _ in range(q):
		(a, b) = map(int, input().split())
		for i in range(a, b + 1):
			cd[i] = True
	res = 0
	for _ in range(l, r + 1):
		if any((a and b for (a, b) in zip(reversed(ab), cd))):
			res += 1
		del ab[-1]
	print(res)
main()


(p, q, l, r) = map(int, input().split())
X = set()
Z = set()
for i in range(p):
	(a, b) = map(int, input().split())
	for j in range(a, b + 1):
		X.add(j)
for i in range(q):
	(c, d) = map(int, input().split())
	for j in range(c, d + 1):
		Z.add(j)
ans = 0
for i in range(l, r + 1):
	for j in Z:
		if j + i in X:
			ans += 1
			break
print(ans)


(p, q, l, r) = map(int, input().split(' '))
plist = list()
qlist = list()
for i in range(p):
	plist.append(list(map(int, input().split())))
for i in range(q):
	qlist.append(list(map(int, input().split())))
pset = set()
qset = set()
for j in range(p):
	pset = pset | set(range(plist[j][0], plist[j][1] + 1))
whengetup = 0
for i in range(l, r + 1):
	qset = set()
	for j in range(q):
		qset = qset | set(range(qlist[j][0] + i, qlist[j][1] + i + 1))
	if len(pset & qset) > 0:
		whengetup += 1
print(whengetup)


(p, q, l, r) = map(int, input().split())
z = [0] * 100000
for i in range(p):
	(a, b) = map(int, input().split())
	for j in range(a, b + 1):
		z[j] = 1
summ = 0
acceptable_t = set([])
for i in range(q):
	t = l
	(c, d) = map(int, input().split())
	while t <= r:
		for j in range(c + t, d + t + 1):
			if z[j] == 1:
				acceptable_t.add(t)
				break
		t += 1
print(len(acceptable_t))


input1 = list(map(lambda x: int(x), input().split()))
p = input1[0]
q = input1[1]
l = input1[2]
r = input1[3]
zTimes = []
xTimes = []
for i in range(p):
	z = tuple(map(lambda x: int(x), input().split()))
	zTimes.append(z)
for i in range(q):
	x = tuple(map(lambda x: int(x), input().split()))
	xTimes.append(x)
suitTimes = []
for z in zTimes:
	for x in xTimes:
		left = z[0] - x[1]
		right = z[1] - x[0]
		suitTimes.append((left, right))
resultSet = set([])
for s in suitTimes:
	for i in range(s[0], s[1] + 1):
		if i >= l and i <= r:
			resultSet.add(i)
print(len(resultSet))


R = lambda : map(int, input().split())
(p, q, l, r) = R()
L = [0] * (r + 1)
(A, B) = ([], [])
for i in range(p):
	A.append(list(R()))
for i in range(q):
	B.append(list(R()))
for i in range(p):
	for j in range(q):
		(a, b) = (max(A[i][0] - B[j][1], l), min(r, A[i][1] - B[j][0]))
		for k in range(a, b + 1):
			L[k] = 1
print(L.count(1))


(p, q, l, r) = map(int, input().split())
a = [0] * p
b = [0] * p
c = [0] * q
d = [0] * q
for i in range(p):
	(a[i], b[i]) = map(int, input().split())
for i in range(q):
	(c[i], d[i]) = map(int, input().split())
cnt = 0
for t in range(l, r + 1):
	events = list(map(lambda x: (x + 0, +1), a)) + list(map(lambda x: (x + 0, -1), b)) + list(map(lambda x: (x + t, +1), c)) + list(map(lambda x: (x + t, -1), d))
	events.sort(key=lambda x: (x[0], -x[1]))
	online = 0
	for (_, i) in events:
		online += i
		if online > 1:
			cnt += 1
			break
print(cnt)


(p, q, l, r) = map(int, input().split())
x = set()
y = set()
count = 0
for i in range(p):
	(a, b) = map(int, input().split())
	for t in range(a, b + 1):
		x.add(t)
for i in range(q):
	(a, b) = map(int, input().split())
	for t in range(a, b + 1):
		y.add(t)
for j in range(l, r + 1):
	for h in y:
		if h + j in x:
			count += 1
			break
print(count)


t = list(input().split())
p = int(t[0])
q = int(t[1])
l = int(t[2])
r = int(t[3])
xv = list()
zv = list()
for i in range(p):
	t = list((int(x) for x in input().split()))
	zv += list((x for x in range(t[0], t[1] + 1)))
sv = set(zv)
for i in range(q):
	t = list((int(x) for x in input().split()))
	xv += list((x for x in range(t[0], t[1] + 1)))
c = 0
for i in range(l, r + 1):
	for j in range(q):
		tt = set((x + i for x in xv))
		if tt & sv != set():
			c += 1
			break
print(c)


from math import inf as inf
from math import *
from collections import *
import sys
from itertools import permutations
input = sys.stdin.readline
t = 1
while t:
	t -= 1
	(p, q, l, r) = map(int, input().split())
	fi = []
	for i in range(p):
		(a, b) = map(int, input().split())
		fi.append([a, b])
	se = []
	for i in range(q):
		(a, b) = map(int, input().split())
		se.append([a, b])
	co = 0
	for i in range(l, r + 1):
		fl = 0
		for j in range(q):
			for k in range(p):
				(le, re) = (se[j][0] + i, se[j][1] + i)
				(x, y) = (fi[k][0], fi[k][1])
				if le >= x and le <= y or (re >= x and re <= y) or (le >= x and re <= y) or (le <= x and re >= y):
					fl = 1
					co += 1
					break
			if fl:
				break
	print(co)


import sys

def solve():
	inp = sys.stdin.read()
	mylist = inp.splitlines()
	(p, q, l, r) = [int(elem) for elem in mylist[0].split(' ')]
	times = list()
	z_times = list()
	x_times = list()
	count = 0
	for elem in mylist[1:]:
		(first, last) = elem.split(' ')
		times.append(list(range(int(first), int(last) + 1)))
	for elem in times[0:p]:
		z_times = z_times + elem
	for elem in times[p:]:
		x_times = x_times + elem
	for i in range(l, r + 1):
		x_new = [x + i for x in x_times]
		for j in x_new:
			if j in z_times:
				count += 1
				break
	print(count)

def main():
	solve()
main()


(p, q, l, r) = list(map(int, input().split()))
bestMoments = 0

def enter(stringNum):
	res = []
	for st in range(stringNum):
		(a, b) = list(map(int, input().split()))
		for i in range(a, b + 1):
			res.append(i)
	return res
littleY = []
littleZ = []
littleY = enter(p)
littleZ = enter(q)
lenYandZ = len(littleY) + len(littleZ)
for i in range(l, r + 1):
	currentZ = list([x + i for x in littleZ])
	if len(set(currentZ + littleY)) < lenYandZ:
		bestMoments += 1
print(bestMoments)


def read_to_list(count):
	s = []
	for i in range(count):
		(start, stop) = [int(i) for i in input().split()]
		s.extend(list(range(start, stop + 1)))
	return s

def has_equal_items(first, second):
	for item in first:
		if item in second:
			return True
	return False

def update_list(l, t):
	for i in range(len(l)):
		l[i] += t

def main():
	(p, q, l, r) = [int(i) for i in input().split()]
	(z, x) = (read_to_list(p), read_to_list(q))
	if l > 0:
		update_list(x, l)
	count = 1 if has_equal_items(z, x) else 0
	for t in range(l, r):
		update_list(x, 1)
		if has_equal_items(x, z):
			count += 1
	print(count)
main()


R = lambda : map(int, input().split())
(p, q, l, r) = R()
a = [0] * 1001
b = [0] * 1001
for _ in range(p):
	(x, y) = R()
	for i in range(x, y + 1):
		a[i] = 1
for _ in range(q):
	(x, y) = R()
	for i in range(x, y + 1):
		b[i] = 1
count = 0
for i in range(l, r + 1):
	if sum((a[j] == 1 and b[j - i] == 1 for j in range(i, 1001))) > 0:
		count += 1
print(count)


from sys import stdin
(p, q, l, r) = map(int, stdin.readline().split())
a = [0] * 1001
x = []
for i in range(p):
	x.append(list(map(int, stdin.readline().split())))
y = []
for i in range(q):
	y.append(list(map(int, stdin.readline().split())))
count = 0
for i in range(p):
	for j in range(q):
		for k in range(max(l, x[i][0] - y[j][1]), min(r, x[i][1] - y[j][0]) + 1):
			a[k] = 1
count = 0
for i in a:
	if i == 1:
		count += 1
print(count)


(p, q, l, r) = [int(i) for i in input().split()]
(P, Q) = (set(), [])
counter = [False for i in range(l, r + 1)]
for i in range(p):
	tmp = [int(j) for j in input().split()]
	P.update(range(tmp[0], tmp[1] + 1))
for i in range(q):
	tmp = [int(j) for j in input().split()]
	Q.append(list(range(tmp[0], tmp[1] + 1)))
for i in range(l, r + 1):
	for j in Q:
		for k in j:
			if k + i in P:
				counter[i - l] = True
				break
print(counter.count(True))


import sys
inf = float('inf')
(mod, MOD) = (1000000007, 998244353)
from collections import deque, Counter, OrderedDict, defaultdict

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()
(p, q, l, r) = get_ints()
X = {}
X = defaultdict(lambda : False, X)
for i in range(p):
	(start, end) = get_ints()
	for i in range(start, end + 1):
		X[i] = True
store = []
for i in range(q):
	(start, end) = get_ints()
	store.append([start, end])
ans = 0
for i in range(l, r + 1):
	flag = 0
	for j in store:
		new_start = j[0] + i
		new_end = j[1] + i
		for k in range(new_start, new_end + 1):
			if X[k]:
				flag = 1
				break
		if flag == 1:
			ans += 1
			break
print(ans)


(p, q, n, r) = map(int, input().split())
l = [0] * 1001
m = [0] * 1001
for i in range(p):
	(a, b) = map(int, input().split())
	for j in range(a, b + 1):
		l[j] = 1
for i in range(q):
	(c, d) = map(int, input().split())
	for j in range(c, d + 1):
		m[j] = 1
t = 0
u = 0
k = []
while t < n:
	k.append(0)
	t += 1
m = k + m
while t <= r:
	for i in range(n, b + 1):
		if l[i] == m[i] == 1:
			u += 1
			break
	m.insert(0, 0)
	t += 1
print(u)


(p, q, l, r) = map(int, input().split())
ps = []
for i in range(p):
	temp = []
	(a, b) = map(int, input().split())
	temp.append(a)
	temp.append(b)
	ps.append(temp)
qs = []
for i in range(q):
	temp = []
	(a, b) = map(int, input().split())
	temp.append(a)
	temp.append(b)
	qs.append(temp)
a = [0] * 1001
b = [0] * 1001
for i in range(p):
	x = ps[i][0]
	y = ps[i][1]
	for j in range(x, y + 1):
		a[j] = 1
count = 0
for i in range(l, r + 1):
	for j in range(q):
		if i == l:
			qs[j][0] += i
			qs[j][1] += i
		else:
			qs[j][0] += 1
			qs[j][1] += 1
	for j in range(q):
		xs = qs[j][0]
		ys = qs[j][1]
		for k in range(xs, ys + 1):
			if k < 1001:
				b[k] = 1
	done = 0
	for j in range(1001):
		if a[j] == 1 and b[j] == 1:
			done = 1
			break
	if done == 1:
		count += 1
	for k in range(1001):
		b[k] = 0
print(count)


(p, q, l, r) = map(int, input().split())
x = []
for i in range(p):
	x.append(list(map(int, input().split())))
y = []
for i in range(q):
	y.append(list(map(int, input().split())))
ans = 0
for i in range(l, r + 1):
	f = 0
	for j in x:
		for k in y:
			if k[0] + i <= j[0] and k[1] + i >= j[0]:
				f = 1
			if k[0] + i >= j[0] and k[0] + i <= j[1]:
				f = 1
	if f:
		ans += 1
print(ans)


(p, q, x, y) = map(int, input().split())
a = [0 for i in range(p)]
b = [0 for i in range(p)]
c = [0 for i in range(q)]
d = [0 for i in range(q)]
for i in range(p):
	(a[i], b[i]) = map(int, input().split())
for i in range(q):
	(c[i], d[i]) = map(int, input().split())
ans = 0

def comp(k, l, m, n):
	if m <= l and k <= n:
		return 0
	elif m >= l:
		return 1
	else:
		return -1
for t in range(x, y + 1):
	i = 0
	j = 0
	while i < p and j < q:
		z = comp(a[i], b[i], c[j] + t, d[j] + t)
		if z == 0:
			ans += 1
			break
		elif z == 1:
			i += 1
		else:
			j += 1
print(ans)


def check(t, p, q):
	for (a, b) in p:
		for (c, d) in q:
			if b < c + t or d + t < a:
				continue
			return 1
	return 0

def check2(t, p, q):
	i = j = 0
	while i < len(p) and j < len(q):
		(a, b, c, d) = p[i] + q[j]
		if a <= c + t <= b or a <= d + t <= b:
			return 1
		if b < c + t:
			i += 1
		elif d + t < a:
			j += 1
		else:
			return 1
	return 0

def solve(p, q, l, r):
	return sum([check2(t, p, q) for t in range(l, r + 1)])
f = lambda st: list(map(int, st.split()))
(p, q, l, r) = f(input())
res = solve([f(input()) for _ in range(p)], [f(input()) for _ in range(q)], l, r)
print(res)


x1 = []
x2 = []
(p, q, l, r) = map(int, input().split(' '))
for i in range(p):
	(a, b) = map(int, input().split(' '))
	x1.append([a, b])
for i in range(q):
	(a, b) = map(int, input().split(' '))
	x2.append([a, b])
ok2 = []
for a in x1:
	for b in x2:
		lo = a[0] - b[1]
		hi = a[1] - b[0]
		if hi >= r:
			hi = r
		if lo <= l:
			lo = l
		ok2.append([lo, hi])
ok = [i for i in ok2 if i[1] >= i[0]]
ok.sort()
total = 0
if len(ok) == 0:
	print(0)
else:
	intv = ok[0]
	for i in range(1, len(ok)):
		curr = ok[i]
		if curr[0] > intv[1]:
			if intv[1] == intv[0]:
				total += 1
			else:
				total += intv[1] - intv[0] + 1
			intv = curr
		else:
			minim = [min(curr[0], intv[0]), max(curr[1], intv[1])]
			intv = minim
	if intv[1] == intv[0]:
		total += 1
	else:
		total += intv[1] - intv[0] + 1
	print(total)


g = input()
(p, q, l, r) = [int(x) for x in g.split()]
pli = []
qli = []
for i in range(p):
	t = input()
	(e, r2) = [int(y) for y in t.split()]
	for u in range(e, r2 + 1):
		pli.append(u)
for i in range(q):
	t1 = input()
	(e1, r1) = [int(y1) for y1 in t1.split()]
	for u1 in range(e1, r1 + 1):
		qli.append(u1)
result = 0
t = l
while r >= t:
	for h in qli:
		if h + t in pli:
			result += 1
			break
	t += 1
print(result)


import sys

def input():
	return sys.stdin.readline().strip()

def iinput():
	return int(input())

def rinput():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))
mod = int(1000000000.0) + 7
(p, q, l, r) = rinput()
ab = []
cd = []
x = [0] * 1001
z = [0] * 1001
for _ in range(p):
	(a, b) = rinput()
	for i in range(a, b + 1):
		z[i] = 1
for _ in range(q):
	(c, d) = rinput()
	for i in range(c, d + 1):
		x[i] = 1
ans = 0
for t in range(l, r + 1):
	for j in range(1001 - t):
		if z[t + j] and x[j]:
			ans += 1
			break
print(ans)


(p, q, l, r) = map(int, input().split())
l1 = []
l2 = []
for i in range(p):
	l1.append(list(map(int, input().split())))
for i in range(q):
	l2.append(list(map(int, input().split())))
count = 0
for a in range(l, r + 1):
	k = 0
	for i in range(p):
		for j in range(q):
			if l1[i][0] <= l2[j][0] + a and l1[i][1] >= l2[j][0] + a:
				k = 1
				count += 1
			elif l1[i][0] <= l2[j][1] + a and l1[i][1] >= l2[j][1] + a:
				k = 1
				count += 1
			elif l1[i][0] >= l2[j][0] + a and l1[i][1] <= l2[j][1] + a:
				k = 1
				count += 1
			if k == 1:
				break
		if k == 1:
			break
print(count)


(p, q, l, r) = map(int, input().split())
ab = [None for _ in range(p)]
for i in range(p):
	(ai, bi) = map(int, input().split())
	ab[i] = (ai, bi)
cd = [None for _ in range(q)]
for i in range(q):
	(ci, di) = map(int, input().split())
	cd[i] = (ci, di)
count = 0
for i in range(l, r + 1):
	flag = False
	for j in range(p):
		for k in range(q):
			if not (cd[k][0] + i > ab[j][1] or cd[k][1] + i < ab[j][0]):
				flag = True
				break
		if flag:
			break
	if flag:
		count += 1
print(count)


(p, q, l, r) = list(map(int, input().split()))
x = [0] * 10000
y = []
cnt = 0
for i in range(p):
	(a, b) = list(map(int, input().split()))
	for j in range(a, b + 1):
		x[j] = 1
for i in range(q):
	(a, b) = list(map(int, input().split()))
	y.append((a, b))
for i in range(l, r + 1):
	f = 0
	for j in range(q):
		if not f:
			for k in range(y[j][0] + i, y[j][1] + i + 1):
				if x[k]:
					f = 1
					break
		else:
			break
	cnt += f
print(cnt)


(p, q, l, r) = map(int, input().split())
z = []
x = []
for i in range(p):
	(a, b) = map(int, input().split())
	for i in range(a, b + 1):
		z.append(i)
for i in range(q):
	(c, d) = map(int, input().split())
	for i in range(c, d + 1):
		x.append(i)

def overlap(a, b, t):
	for i in b:
		if i + t in a:
			return True
	return False
counter = 0
for i in range(l, r + 1):
	if overlap(z, x, i):
		counter += 1
print(counter)


(p, q, l, r) = map(int, input().split())
tim = [0] * 10006
for i in range(p):
	(a, b) = map(int, input().split())
	for _ in range(a, b + 1):
		tim[_] = 1
lis = []
ans = 0
for i in range(q):
	(c, d) = map(int, input().split())
	lis.append([c, d])
for i in range(l, r + 1):
	for j in lis:
		(a, b) = j
		if max(tim[a + i:b + 1 + i]) == 1:
			ans += 1
			break
print(ans)


(p, q, l, r) = [int(i) for i in input().split()]
ans = 0
mark_z = set()
mark_x = set()
for i in range(p):
	tmp = [int(j) for j in input().split()]
	for i in range(tmp[0], tmp[1] + 1):
		mark_z.add(i)
for i in range(q):
	tmp = [int(j) for j in input().split()]
	for i in range(tmp[0], tmp[1] + 1):
		mark_x.add(i)
for i in range(l, r + 1):
	for j in mark_x:
		if j + i in mark_z:
			ans += 1
			break
print(ans)


import sys
import os
input = sys.stdin.buffer.readline
(p, q, l, r) = map(int, input().split())
ab = []
cd = []
while p:
	p -= 1
	(a, b) = map(int, input().split())
	for j in range(a, b + 1):
		ab.append(j)
ab = set(ab)
while q:
	q -= 1
	(c, d) = map(int, input().split())
	cd.append([c, d])
i = l
count = 0
while i < r + 1 and count != l - r + 1:
	check = []
	for l in range(len(cd)):
		for j in range(cd[l][0] + i, cd[l][1] + i + 1):
			check.append(j)
	check = set(check)
	another = list(ab.intersection(check))
	if len(another) > 0:
		count += 1
	i += 1
print(count)


(p, q, l, r) = [int(i) for i in input().split()]
cnt = 0
Z = []
X = []
temp = []
for i in range(p):
	Z.append([int(i) for i in input().split()])
for i in range(q):
	X.append([int(i) for i in input().split()])
for i in X:
	temp.append([j + l for j in list(i)])
X = temp
for t in range(l, r + 1):
	b = False
	for i in Z:
		for j in X:
			if min(i) <= min(j) <= max(i) or min(i) <= max(j) <= max(i) or min(j) <= min(i) <= max(j) or (min(j) <= max(i) <= max(j)):
				b = True
				break
		if b:
			cnt += 1
			break
	x = []
	for i in X:
		x.append([j + 1 for j in list(i)])
	X = x
print(cnt)


(p, q, l, r) = map(int, input().split())
(x, y) = (set(), set())
for i in range(p):
	(j, k) = map(int, input().split())
	[x.add(n) for n in range(j, k + 1)]
for i in range(q):
	(j, k) = map(int, input().split())
	[y.add(n) for n in range(j, k + 1)]
p = 0
for i in range(l, r + 1):
	for j in y:
		if j + i in x:
			p += 1
			break
print(p)


import math
(p, q, l, r) = map(int, input().split())
lz = []
lx = []
for i in range(p):
	lz.append(list(map(int, input().split())))
for i in range(q):
	lx.append(list(map(int, input().split())))
ans = 0
lst = set()
for a in lz:
	for b in lx:
		for i in range(l, r + 1):
			(x, y) = (b[0], b[1])
			(x, y) = (x + i, y + i)
			if y >= a[1] and x <= a[0] or a[0] <= y <= a[1] or a[0] <= x <= a[1]:
				lst.add(i)
print(len(lst))


from sys import stdin
(p, q, l, r) = map(int, stdin.readline().split())
z_list = []
x_list = []
for x in range(p):
	(i, j) = map(int, stdin.readline().split())
	for x in range(i, j + 1):
		z_list.append(x)
for x in range(q):
	(i, j) = map(int, stdin.readline().split())
	for x in range(i, j + 1):
		x_list.append(x)
t = l
ans = 0
for x in range(l, r + 1):
	xt_list = [x + t for x in x_list]
	t += 1
	if len(list(set(z_list) & set(xt_list))) != 0:
		ans += 1
print(ans)


from sys import stdin
from itertools import chain
(p, q, l, r) = map(int, stdin.readline().rstrip().split())
x_times = set()
z_times = []
for i in range(p):
	(s, e) = map(int, stdin.readline().rstrip().split())
	x_times |= set(range(s, e + 1))
for i in range(q):
	(s, e) = map(int, stdin.readline().rstrip().split())
	z_times.append((s, e + 1))
count = 0
for t in range(l, r + 1):
	z_t_times = set(chain.from_iterable((range(t + s, t + e) for (s, e) in z_times)))
	if x_times & z_t_times:
		count += 1
print(count)


(p, q, l, r) = map(int, input().split())
ans = 0
xx = set()
zz = set()
for i in range(p):
	tmp = list(map(int, input().split()))
	for j in range(tmp[0], tmp[1] + 1):
		zz.add(j)
for i in range(q):
	tmp = list(map(int, input().split()))
	for j in range(tmp[0], tmp[1] + 1):
		xx.add(j)
for i in range(l, r + 1):
	for j in xx:
		if i + j in zz:
			ans += 1
			break
print(ans)


(p, q, l, r) = map(int, input().split())
ptimes = []
qtimes = []
genp = []
genq = []
for inp in range(p):
	ptimes.append([int(z) for z in input().split()])
	for i in range(ptimes[inp][0], ptimes[inp][1] + 1):
		genp.append(i)
for inp in range(q):
	qtimes.append([int(z) for z in input().split()])
	for i in range(qtimes[inp][0], qtimes[inp][1] + 1):
		genq.append(i)
cnt = 0
for up in range(l, r + 1):
	genq1 = genq[:]
	for i in range(len(genq)):
		genq1[i] += up
	lst = genp + genq1
	if len(set(lst)) < len(lst):
		cnt += 1
print(cnt)


(p, q, l, r) = map(int, input().split())
(x, y) = (set(), set())
for i in range(p):
	(a, b) = map(int, input().split())
	[x.add(n) for n in range(a, b + 1)]
for i in range(q):
	(c, d) = map(int, input().split())
	[y.add(n) for n in range(c, d + 1)]
p = 0
for i in range(l, r + 1):
	for j in y:
		if j + i in x:
			p += 1
			break
print(p)


l1 = [int(x) for x in input().split()]
p = l1[0]
q = l1[1]
l = l1[2]
r = l1[3]
l2 = []
l4 = []
for i in range(0, p):
	l3 = [int(x) for x in input().split()]
	l2.append(l3)
for i in range(0, q):
	l3 = [int(x) for x in input().split()]
	l4.append(l3)
count = 0
for j in range(l, r + 1):
	matched = False
	for k in range(0, len(l4)):
		for x in range(0, len(l2)):
			if l2[x][1] < l4[k][0] + j:
				continue
			elif l4[k][1] + j < l2[x][0]:
				continue
			else:
				count += 1
				matched = True
				break
		if matched == True:
			break
print(count)


(p, q, l, r) = map(int, input().split(' '))
c = [0] * 1001
m = 0
for i in range(p):
	(a, b) = map(int, input().split(' '))
	m = max(a, b, m)
	for j in range(a, b + 1):
		c[j] = 1
d = [0] * 1001
for i in range(q):
	(a, b) = map(int, input().split(' '))
	for j in range(a, b + 1):
		d[j] = 1
for i in range(0, l):
	d.pop()
	d.insert(0, 0)
k = 0
for i in range(l, r + 1):
	for j in range(i, m + 1):
		if c[j] == 1 and d[j] == 1:
			k += 1
			break
	d.pop()
	d.insert(0, 0)
print(k)


(p, q, l, r) = map(int, input().split())
z = []
x = []
for i in range(p):
	(a, b) = map(int, input().split())
	z.append([a, b])
for i in range(q):
	(c, d) = map(int, input().split())
	x.append([c, d])
s = [i for i in range(l, r + 1)]
s = set(s)
lr = set()
for j in z:
	for i in x:
		add = []
		if i[0] > j[1]:
			continue
		elif i[0] >= j[0]:
			add.extend([t for t in range(0, j[1] - i[0] + 1)])
		elif i[1] >= j[0]:
			add.extend([t for t in range(0, j[1] - i[0] + 1)])
		elif i[1] < j[0]:
			add.extend([t for t in range(j[0] - i[1], j[1] - i[0] + 1)])
		m = set(add)
		lr = lr.union(m)
print(len(s.intersection(lr)))


def check(j):
	for i in range(0, len(arr), 2):
		for k in range(arr[i] + j, arr[i + 1] + j + 1):
			if lis[k] != 0:
				return True
	return False
(p, q, l, r) = map(int, input().split())
lis = [0] * 2001
while p:
	p -= 1
	(a, b) = map(int, input().split())
	lis[a] += 1
	lis[b + 1] -= 1
for k in range(1, len(lis)):
	lis[k] = lis[k] + lis[k - 1]
arr = []
while q:
	q -= 1
	(c, d) = map(int, input().split())
	arr.append(c)
	arr.append(d)
arr.sort()
count = 0
for j in range(l, r + 1):
	if check(j):
		count += 1
print(count)


def main():
	(p, q, l, r) = map(int, input().split())
	(ab, cd) = ([False] * 1001, [False] * 1001)
	for _ in range(p):
		(a, b) = map(int, input().split())
		for i in range(a, b + 1):
			ab[i] = True
	for _ in range(q):
		(a, b) = map(int, input().split())
		for i in range(a, b + 1):
			cd[i] = True
	res = 0
	for i in range(l, r + 1):
		for t in range(i, 1001):
			if ab[t] and cd[t - i]:
				res += 1
				break
	print(res)
main()


(p, q, l, r) = map(int, input().split())
arr_z = [0] * (p * 2)
i = 0
for k in range(p):
	t = list(map(int, input().split()))
	(arr_z[i], arr_z[i + 1]) = ((t[0], -1), (t[1], 1))
	i += 2
arr_z.sort()
arr = [False] * 1001
for i in range(q):
	t = list(map(int, input().split()))
	t[1] = t[1] - t[0]
	f = t[0]
	for j in range(l, r + 1):
		t[0] = f + j
		if arr[j] != True:
			tl = -1
			tr = p * 2
			while tr > tl + 1:
				m = (tr + tl) // 2
				if t[0] < arr_z[m][0]:
					tr = m
				elif t[0] > arr_z[m][0]:
					tl = m
				elif arr_z[m][1] == 1:
					tr = m
				else:
					tl = m
			if tr < p * 2 and arr_z[tr][0] <= t[0] + t[1] or (tr != 0 and arr_z[tr - 1][1] == -1):
				arr[j] = True
ans = 0
for i in arr[l:r + 1]:
	if i == True:
		ans += 1
print(ans)


(p, q, l, r) = [int(x) for x in input().split()]
f = []
for i in range(p):
	f.append([int(x) for x in input().split()])
s = []
for i in range(q):
	s.append([int(x) for x in input().split()])
t = 0
flag = False
for i in range(l, r + 1):
	flag = False
	for (x, y) in s:
		c = x + i
		d = y + i
		for (x2, y2) in f:
			if x2 >= c and x2 <= d or (c >= x2 and c <= y2):
				t += 1
				flag = True
				break
		if flag:
			break
print(t)


import sys

def overlap(ap, bp, cq, dq, t):
	if t + dq < ap:
		return False
	if t + cq > bp:
		return False
	return True

def any_interval(a, b, c, d, t):
	for p in range(len(a)):
		for q in range(len(c)):
			if overlap(a[p], b[p], c[q], d[q], t):
				return True
	return False
data = input().split(' ')
P = int(data[0])
Q = int(data[1])
l = int(data[2])
r = int(data[3])
(a, b, c, d) = ([], [], [], [])
for i in range(P):
	data = input().split(' ')
	a.append(int(data[0]))
	b.append(int(data[1]))
for i in range(Q):
	data = input().split(' ')
	c.append(int(data[0]))
	d.append(int(data[1]))
count = 0
for t in range(l, r + 1):
	if any_interval(a, b, c, d, t):
		count += 1
print(count)


(p, q, l, r) = map(int, input().split())
l1 = []
lis = []
c1 = 0
for _ in range(p):
	(a, b) = map(int, input().split())
	l1 += [x for x in range(a, b + 1)]
for _ in range(q):
	(c, d) = map(int, input().split())
	lis += [x for x in range(c, d + 1)]
t = l
while r >= t:
	for h in lis:
		if h + t in l1:
			c1 += 1
			break
	t += 1
print(c1)


from __future__ import division, print_function
import math
import os
import sys
from sys import stdin, stdout
from io import BytesIO, IOBase
from itertools import accumulate
from collections import deque
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def regularbracket(t):
	p = 0
	for i in t:
		if i == '(':
			p += 1
		else:
			p -= 1
		if p < 0:
			return False
	else:
		if p > 0:
			return False
		else:
			return True

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def reverse1(string):
	pp = ''
	for i in string[::-1]:
		pp += i
	if pp == string:
		return True
	return False

def reverse2(list1):
	l = []
	for i in list1[::-1]:
		l.append(i)
	if l == list1:
		return True
	return False
import math

def mex(list1):
	p = max(list1) + 1
	for i in range(len(list1)):
		if list1[i] != i:
			p = i
			break
	return p

def main():
	(p, q, l, r) = map(int, input().split())
	ll = []
	pp = []
	for _ in range(p):
		(a, b) = map(int, input().split())
		for i in range(a, b + 1):
			ll.append(i)
	for _ in range(q):
		(c, d) = map(int, input().split())
		for i in range(c, d + 1):
			pp.append(i)
	cnt = 0
	for i in range(l, r + 1):
		for j in pp:
			if j + i in ll:
				cnt += 1
				break
	print(cnt)
main()


def shift(S, i):
	return set((x + i for x in S))
(p, q, l, r) = [int(x) for x in input().split()]
(P, Q) = (set(), set())
for i in range(p):
	(a, b) = [int(x) for x in input().split()]
	P.update(range(a, b + 1))
for i in range(q):
	(a, b) = [int(x) for x in input().split()]
	Q.update(range(a, b + 1))
ans = 0
for i in range(l, r + 1):
	if shift(Q, i) & P:
		ans += 1
print(ans)


(p, q, l, r) = tuple(map(int, input().split(' ')))
IP = [False] * 1001
IQ = [False] * 1001
for i in range(p):
	(a, b) = tuple(map(int, input().split(' ')))
	IP[a:b + 1] = [True] * (b - a + 1)
for i in range(q):
	(a, b) = tuple(map(int, input().split(' ')))
	IQ[a:b + 1] = [True] * (b - a + 1)
li = []
li = (1 for i in range(l, r + 1) if any((True for j in range(1001 - i) if IP[i + j] and IQ[j])))
print(sum(li))


(p, q, l, r) = input().split(' ')
cd = []
ab = [0] * 1001
for i in range(int(p)):
	(a, b) = input().split(' ')
	for j in range(int(a), int(b) + 1):
		ab[j] = 1
for i in range(int(q)):
	cd.append([int(x) for x in input().split(' ')])
count = 0
for i in range(int(l), int(r) + 1):
	flag = False
	for j in range(int(q)):
		for k in range(cd[j][0] + i, cd[j][1] + i + 1):
			if k <= 1000 and ab[k]:
				flag = True
				break
	if flag:
		count += 1
print(count)


(p, q, l, r) = map(int, input().split())
(x, z) = ([False] * 1001, [False] * 1001)
count = 0
for i in range(p):
	(m, n) = map(int, input().split())
	z[m:n + 1] = [True] * (n + 1 - m)
for i in range(q):
	(m, n) = map(int, input().split())
	x[m:n + 1] = [True] * (n + 1 - m)
li = []
li = (1 for i in range(l, r + 1) if any((True for j in range(1001 - i) if z[i + j] and x[j])))
print(sum(li))


(p, q, l, r) = list(map(int, input().split()))
z = []
x = []
a = 0
for i in range(p):
	z.append(list(map(int, input().split())))
for i in range(q):
	x.append(list(map(int, input().split())))
Z = []
X = []
for i in range(p):
	for j in range(z[i][0], z[i][1] + 1):
		Z.append(j)
for i in range(q):
	for j in range(x[i][0], x[i][1] + 1):
		X.append(j)
n = len(X)
m = len(Z)
for i in range(l, r + 1):
	if i == l:
		for j in range(n):
			X[j] = X[j] + i
	else:
		for j in range(n):
			X[j] = X[j] + 1
	j = 0
	k = 0
	c = 0
	while j < n and k < m:
		if X[j] < Z[k]:
			j = j + 1
		elif X[j] > Z[k]:
			k = k + 1
		else:
			j = j + 1
			k = k + 1
			c = c + 1
	if c:
		a = a + 1
print(a)


(p, q, l, r) = map(int, input().split())
(z_s, x_s) = (set(), set())
for __ in range(p):
	(a, b) = map(int, input().split())
	for i in range(a, b + 1):
		z_s.add(i)
for __ in range(q):
	(c, d) = map(int, input().split())
	for i in range(c, d + 1):
		x_s.add(i)
count = 0
for i in range(l, r + 1):
	if i > max(z_s):
		break
	for j in x_s:
		if j + i in z_s:
			count += 1
			break
print(count)


(p, q, l, r) = [int(x) for x in input().split()]
ab = []
for _ in range(p):
	ab.append([int(x) for x in input().split()])
cd = []
for _ in range(q):
	cd.append([int(x) for x in input().split()])
count = 0
s = set()
for t in range(l, r + 1):
	common_time = False
	for x in cd:
		ci = x[0] + t
		di = x[1] + t
		for y in ab:
			ai = y[0]
			bi = y[1]
			if ci <= ai <= di or ai <= ci <= bi:
				count += 1
				s.add((ai, bi, ci, di))
				common_time = True
				break
		if common_time:
			break
print(count)


(p, q, l, r) = map(int, input().split())
littleX = []
littleZ = []
for p1 in range(p):
	(a, b) = map(int, input().split())
	littleZ.append([a, b])
for q1 in range(q):
	(a, b) = map(int, input().split())
	littleX.append([a, b])
accept_t = set()
for t in range(l, r + 1):
	for ttX in littleX:
		a1 = ttX[0] + t
		b1 = ttX[1] + t
		for ttZ in littleZ:
			c1 = ttZ[0]
			d1 = ttZ[1]
			if a1 >= c1 and a1 <= d1 or (b1 >= c1 and b1 <= d1) or (c1 >= a1 and c1 <= b1) or (d1 >= a1 and d1 <= b1):
				accept_t.add(t)
print(len(accept_t))


(p, q, l, r) = map(int, input().split())
lst = []
lst1 = []
cnt = f = 0
for i in range(p):
	(n, m) = map(int, input().split())
	lst.append([n, m])
for i in range(q):
	(n, m) = map(int, input().split())
	lst1.append([n, m])
for i in range(l, r + 1):
	for j in range(q):
		for k in range(p):
			if lst[k][0] <= lst1[j][1] + i and lst[k][1] >= lst1[j][0] + i:
				cnt += 1
				f = 1
				break
		if f == 1:
			f = 0
			break
print(cnt)


import math
from collections import defaultdict
ml = lambda : map(int, input().split())
ll = lambda : list(map(int, input().split()))
ii = lambda : int(input())
ip = lambda : input()
ips = lambda : input().split()

def shift(s, l):
	for i in range(2000, l - 1, -1):
		s[i] = s[i - l]
	for j in range(l):
		s[j] = '0'
t = 1
for _ in range(t):
	(p, q, l, r) = ml()
	a = []
	b = []
	s1 = ''
	s2 = ''
	d = defaultdict(int)
	D = defaultdict(int)
	for i in range(p):
		(x, y) = ml()
		a.append([x, y])
		for j in range(x, y + 1):
			d[j] = 1
	for i in range(q):
		(x, y) = ml()
		b.append([x, y])
		for j in range(x, y + 1):
			D[j] = 1
	for i in range(2001):
		if d[i]:
			s1 += '1'
		else:
			s1 += '0'
		if D[i]:
			s2 += '1'
		else:
			s2 += '0'
	s1 = list(s1)
	s2 = list(s2)
	shift(s2, l)
	ans = 0
	for i in range(l, r + 1):
		f = 0
		if i > l:
			shift(s2, 1)
		for j in range(2001):
			if s2[j] == '1' and s1[j] == '1':
				f = 1
				break
		if f:
			ans += 1
	print(ans)


(p, q, l, r) = map(int, input().split())
t1 = [0] * 1001
for _ in range(p):
	(x, y) = map(int, input().split())
	for i in range(x, y + 1):
		t1[i] = 1
t2 = [0] * 1001
for _ in range(q):
	(x, y) = map(int, input().split())
	for i in range(x, y + 1):
		t2[i] = 1
ans = 0
for d in range(l, r + 1):
	i = 0
	while i < 1001 and i + d < 1001:
		if t2[i] and t1[i + d]:
			ans += 1
			break
		i += 1
print(ans)


(p, q, l, r) = map(int, input().split())
z = []
for _ in range(p):
	(a, b) = map(int, input().split())
	z.append([a, b])
x = []
for _ in range(q):
	(c, d) = map(int, input().split())
	x.append([c, d])
count = 0
flag = 0
for i in range(l, r + 1):
	for j in range(len(x)):
		(l1, r1) = (x[j][0] + i, x[j][1] + i)
		for k in range(len(z)):
			(l2, r2) = (z[k][0], z[k][1])
			if l2 > r1 or r2 < l1:
				continue
			else:
				flag = 1
				break
		if flag == 1:
			count += 1
			flag = 0
			break
print(count)


(p, q, l1, r) = map(int, input().split())
k = set()
for i in range(p):
	(c, d) = map(int, input().split())
	for i in range(c, d + 1):
		k.add(i)
l = set()
for i in range(q):
	(c, d) = map(int, input().split())
	for i in range(c, d + 1):
		l.add(i)
l = list(l)
l.sort()
count = 0
for i in range(l1, r + 1):
	for j in range(len(l)):
		if l[j] + i in k:
			count += 1
			break
print(count)


(p, q, l, r) = list(map(int, input().split()))
z = []
for i in range(p):
	z.append(list(map(int, input().split())))
x = []
for i in range(q):
	x.append(list(map(int, input().split())))
count = 0
for i in range(l, r + 1):
	flag = False
	for (c, d) in x:
		for (a, b) in z:
			if c + i <= b and d + i >= a:
				flag = True
				break
		if flag:
			count += 1
			break
print(count)


from sys import stdin, stdout
ii1 = lambda : int(stdin.readline().strip())
is1 = lambda : stdin.readline().strip()
iia = lambda : list(map(int, stdin.readline().strip().split()))
isa = lambda : stdin.readline().strip().split()
mod = 1000000007
(p, q, l, r) = iia()
(x, y) = ([], [])
for _ in range(p):
	x.append(iia())
for _ in range(q):
	y.append(iia())
time = 0
for i in range(l, r + 1):
	for j in y:
		(a, b) = (j[0] + i, j[1] + i)
		meet = False
		for k in x:
			if range(max(k[0], a), min(k[-1], b) + 1):
				time += 1
				meet = True
				break
		if meet:
			break
print(time)


(p, q, l, r) = map(int, input().split(' '))
z = [0 for _ in range(1001)]
x = [0 for _ in range(1001)]
for _ in range(p):
	(a, b) = map(int, input().split(' '))
	for i in range(a, b + 1):
		z[i] = 1
for _ in range(q):
	(a, b) = map(int, input().split(' '))
	for i in range(a, b + 1):
		x[i] = 1
count = 0
for i in range(l, r + 1):
	temp = [0 for _ in range(i)] + x
	match = False
	for j in range(1001):
		if z[j] == 1 and temp[j] == 1:
			match = True
			break
	if match:
		count += 1
print(count)


import sys
input = sys.stdin.buffer.readline
(p, q, l, r) = list(map(int, input().split()))
z = []
x = []
for _ in range(p):
	z.append(list(map(int, input().split())))
contributed = [False] * 1001
for i in range(q):
	(c, d) = list(map(int, input().split()))
	for j in range(p):
		(a, b) = z[j]
		lo = a - d
		hi = b - c
		if hi < 0:
			continue
		elif lo < 0:
			lo = 0
		contributed[lo:hi + 1] = [True] * (hi - lo + 1)
ans = 0
for k in range(l, r + 1):
	if contributed[k]:
		ans += 1
print(ans)


from sys import stdin, stdout

def main():
	z = [0] * 1100
	(p, q, l, r) = map(int, stdin.readline().split())
	for i in range(p):
		(a, b) = map(int, stdin.readline().split())
		z[a:b + 1] = [1 for _ in range(a, b + 1)]
	x = []
	for i in range(q):
		(c, d) = map(int, stdin.readline().split())
		x.append((c, d))
	count = 0
	for i in range(l, r + 1):
		for (c, d) in x:
			if sum(z[c + i:d + i + 1]) >= 1:
				count += 1
				break
	print(count)
main()


try:
	(p, q, l, r) = map(int, input().split())
	(x, y) = ([], [])
	for i in range(p):
		(a, b) = map(int, input().split())
		[x.append(n) for n in range(a, b + 1)]
	x = set(x)
	for i in range(q):
		(c, d) = map(int, input().split())
		[y.append(n) for n in range(c, d + 1)]
	y = set(y)
	cnt = 0
	for i in range(l, r + 1):
		for j in y:
			if j + i in x:
				cnt += 1
				break
	print(cnt)
except:
	pass


def f(x1, y1, x2, y2):
	return x1 <= x2 <= y1 or x1 <= y2 <= y1 or x2 <= x1 <= y2
(p, q, l, r) = list(map(int, input().split()))
(a1, a2) = ([(0, 0)] * p, [(0, 0)] * q)
for i in range(p):
	(a, b) = list(map(int, input().split()))
	a1[i] = (a, b)
for i in range(q):
	(a, b) = list(map(int, input().split()))
	a2[i] = (a, b)
res = [False] * 2000
ans = 0
for i in a1:
	for j in a2:
		for k in range(max(0, i[0] - j[1]), i[1] - j[0] + 1):
			res[k] = True
for i in range(l, r + 1):
	if res[i]:
		ans += 1
print(ans)


(p, q, l, r) = map(int, input().split())
ps = []
qs = []
fixed = []
flexible = []
for i in range(p):
	(a, b) = map(int, input().split())
	fixed = fixed + [x for x in range(a, b + 1)]
for i in range(q):
	(a, b) = map(int, input().split())
	flexible += [x for x in range(a, b + 1)]
fixed = set(fixed)
cnt = 0
for t in range(l, r + 1):
	flexiblet = [t + x for x in flexible]
	flexiblet = set(flexiblet)
	if fixed & flexiblet:
		cnt += 1
print(cnt)


import sys
input = sys.stdin.readline
(p, q, l, r) = map(int, input().split())
little_x = set([])
for _ in range(p):
	(a, b) = map(int, input().split())
	for minute in range(a, b + 1):
		little_x.add(minute)
poss = [0] * (r + 1)
for _ in range(q):
	(a, b) = map(int, input().split())
	for minute in range(a, b + 1):
		for t in range(l, r + 1):
			if minute + t in little_x:
				poss[t] = 1
print(poss[l:].count(1))


(p, q, l, r) = map(int, input().split())
L = [0 for i in range(1001)]
for i in range(p):
	(a, b) = map(int, input().split())
	L[a] += 1
	if b < 1000:
		L[b + 1] -= 1
for i in range(1001):
	L[i] = L[i] + L[i - 1]
K = [0 for i in range(1001)]
for i in range(q):
	(a, b) = map(int, input().split())
	K[a] += 1
	if b < 1000:
		K[b + 1] -= 1
for i in range(1001):
	K[i] = K[i] + K[i - 1]
M = []
for i in range(1001):
	if K[i] > 0:
		M.append(i)
ans = 0
n = len(M)
for i in range(l, r + 1):
	for j in range(n):
		if M[j] + i < 1001:
			if L[M[j] + i] > 0:
				ans += 1
				break
print(ans)


(p, q, l, r) = map(int, input().split())
(a, b) = (set(), set())
for _ in range(p):
	(x, y) = map(int, input().split())
	[a.add(x) for x in range(x, y + 1)]
for _ in range(q):
	(x, y) = map(int, input().split())
	[b.add(x) for x in range(x, y + 1)]
res = 0
for i in range(l, r + 1):
	for x in b:
		if x + i in a:
			res += 1
			break
print(res)


(p, q, l, r) = map(int, input().split())
z_schedules = set()
for _ in range(p):
	(start, end) = map(int, input().split())
	z_schedules.update([i for i in range(start, end + 1)])
x_schedules = set()
for _ in range(q):
	(start, end) = map(int, input().split())
	x_schedules.update([i for i in range(start, end + 1)])
hours = 0
for wake_up in range(l, r + 1):
	for X in x_schedules:
		if X + wake_up in z_schedules:
			hours += 1
			break
print(hours)


(p, q, l, r) = map(int, input().split())
hz = [0 for a in range(10000)]
hx = [0 for b in range(10000)]
for i in range(p):
	(a, b) = map(int, input().strip().split())
	for j in range(a, b + 1):
		hz[j] = 1
for _ in range(q):
	(a, b) = map(int, input().strip().split())
	for j in range(a, b + 1):
		hx[j] = 1
res = 0
for i in range(l, r + 1):
	hx = [0] * i + hx
	for j in range(0, len(hz)):
		if hz[j] == 1 and hx[j] == 1:
			res += 1
			break
	hx = hx[i:]
print(res)


I = lambda : map(int, input().split())
(p, q, l, r) = I()
fixed = []
flexible = []
for _ in range(p):
	(a, b) = I()
	fixed += [x for x in range(a, b + 1)]
for _ in range(q):
	(a, b) = I()
	flexible += [x for x in range(a, b + 1)]
fixed = set(fixed)
count = 0
for t in range(l, r + 1):
	flexiblet = set([x + t for x in flexible])
	if len(fixed & flexiblet) > 0:
		count += 1
print(count)


(p, q, l, r) = [int(x) for x in input().split()]
a = ''
b = ''
for i in range(p):
	(x, y) = [int(x) for x in input().split()]
	a += '0' * (x - len(a))
	a += '1' * (y - x + 1)
for i in range(q):
	(x, y) = [int(x) for x in input().split()]
	b += '0' * (x - len(b))
	b += '1' * (y - x + 1)
ans = 0
for i in range(l, r + 1):
	ans += 1 if any(map(lambda x: x[0] == '1' and x[1] == '1', zip(a, '0' * i + b))) else 0
print(ans)


RMAX = 1000
(p, q, l, r) = map(int, input().split())

def rl():
	(a, b) = map(int, input().split())
	return (a, b)
x = [rl() for _ in range(p)]
xline = [False] * (RMAX + 1)
for (a, b) in x:
	for i in range(a, b + 1):
		xline[i] = True
y = [rl() for _ in range(q)]

def test(t):
	for (a, b) in y:
		for i in range(t + a, t + b + 1):
			if i > RMAX:
				break
			if xline[i] == True:
				return 1
	return 0
ans = sum((test(t) for t in range(l, r + 1)))
print(ans)


(p, q, l, r) = map(int, input().split())
k1 = []
k2 = []
k = []
for i in range(p):
	(a, b) = map(int, input().split())
	k1 += [i for i in range(a, b + 1)]
for i in range(q):
	(a, b) = map(int, input().split())
	k2 += [i for i in range(a, b + 1)]
c = 0
for i in range(l, r + 1):
	for j in k2:
		if j + i in k1:
			c += 1
			break
print(c)


(p, q, l, r) = list(map(int, input().split()))
a = []
for i in range(p):
	(k, j) = list(map(int, input().split()))
	a.append((k, j))
b = []
for i in range(q):
	(k, j) = list(map(int, input().split()))
	b.append((k, j))
b.sort(key=lambda h: h[0])
count = 0
for i in range(l, r + 1):
	for j in range(len(b)):
		gg = 0
		for k in range(len(a)):
			if b[j][0] + i <= a[k][0] <= a[k][1] <= b[j][1] + i or a[k][0] <= b[j][0] + i <= a[k][1] <= b[j][1] + i or b[j][0] + i <= a[k][0] <= b[j][1] + i <= a[k][1] or (a[k][0] <= b[j][0] + i <= b[j][1] + i <= a[k][1]):
				count += 1
				gg = 1
				break
		if gg == 1:
			break
print(count)


def s(a, b):
	return set(range(a, b + 1))
(p, q, l, r) = map(int, input().split())
fixed = set()
movable = set()
for i in range(p):
	(a, b) = map(int, input().split())
	fixed = fixed.union(s(a, b))
for i in range(q):
	(a, b) = map(int, input().split())
	movable = movable.union(s(a, b))
ans = 0
for i in range(l, r + 1):
	movable_new = set([x + i for x in movable])
	if movable_new.intersection(fixed) != set():
		ans += 1
print(ans)


(p, q, l, r) = [int(a) for a in input().split()]
a = []
b = []
c = []
d = []
for i in range(p):
	(aa, bb) = [int(a) for a in input().split()]
	a.append(aa)
	b.append(bb)
for i in range(q):
	(aa, bb) = [int(a) for a in input().split()]
	c.append(aa)
	d.append(bb)
counter = 0
for i in range(l, r + 1):
	j = k = 0
	while j < p and k < q:
		if b[j] < c[k] + i:
			j += 1
		elif d[k] + i < a[j]:
			k += 1
		else:
			counter += 1
			break
print(counter)


(p, q, l, r) = map(int, input().split())
a = []
b = []
count = 0
for i in range(p):
	(n, m) = map(int, input().split())
	a.append([n, m])
for i in range(q):
	(n, m) = map(int, input().split())
	b.append([n, m])
for k in range(l, r + 1):
	flag = True
	for i in a:
		for j in b:
			if i[0] == j[0] + k or i[1] == j[1] + k or j[1] + k == i[0] or (j[0] + k == i[1]) or (i[0] <= j[0] + k <= i[1]) or (i[0] <= j[1] + k <= i[1]) or (j[0] + k <= i[0] <= j[1] + k) or (j[0] + k <= i[0] <= j[1] + k):
				count += 1
				flag = False
				break
		if not flag:
			break
print(count)


def solution():
	(p, q, l, r) = [int(x) for x in input().split(' ')]
	x = []
	y = []
	ans = 0
	for i in range(p):
		x.append([int(_x) for _x in input().split(' ')])
	for i in range(q):
		y.append([int(_x) for _x in input().split(' ')])
	for t in range(l, r + 1):
		current = 0
		found = False
		for (a, b) in x:
			if found:
				break
			for (c, d) in y:
				c += t
				d += t
				if not (a > d or b < c):
					current += max(min(b, d) - max(a, c) + 1, 0)
					if current > 0:
						ans += 1
						found = True
						break
	return ans
print(solution())


import sys
input = sys.stdin.readline
read_tuple = lambda _type: map(_type, input().split(' '))

def solve():
	(p, q, l, r) = read_tuple(int)
	z = [tuple(read_tuple(int)) for _ in range(p)]
	x = [tuple(read_tuple(int)) for _ in range(q)]

	def f(t):
		for (a_s, a_l) in z:
			for (b_s, b_l) in x:
				(b_s, b_l) = (b_s + t, b_l + t)
				if not (b_s > a_l or a_s > b_l):
					return 1
		return 0
	ans = sum((f(t) for t in range(l, r + 1)))
	print(ans)
solve()


temparr = input()
temparr = temparr.split()
p = int(temparr[0])
q = int(temparr[1])
l = int(temparr[2])
r = int(temparr[3])
arrp = []
arrq = []
for i in range(p):
	temparr = input()
	temparr = temparr.split()
	aa = int(temparr[0])
	bb = int(temparr[1])
	arrp.append([aa, bb])
for i in range(q):
	temparr = input()
	temparr = temparr.split()
	aa = int(temparr[0])
	bb = int(temparr[1])
	arrq.append([aa, bb])
arrp = sorted(arrp)
arrq = sorted(arrq)
ans = 0

def swap(i, j):
	return (j, i)
for time in range(l, r + 1):
	flag = 0
	for i in range(q):
		qpair = arrq[i]
		si = qpair[0] + time
		ei = qpair[1] + time
		for j in range(p):
			ppair = arrp[j]
			sj = ppair[0]
			ej = ppair[1]
			if si >= sj and si <= ej:
				flag = 1
				break
			if ei >= sj and ei <= ej:
				flag = 1
				break
			(si, sj) = swap(si, sj)
			(ei, ej) = swap(ei, ej)
			if si >= sj and si <= ej:
				flag = 1
				break
			if ei >= sj and ei <= ej:
				flag = 1
				break
			(si, sj) = swap(si, sj)
			(ei, ej) = swap(ei, ej)
		if flag == 1:
			break
	if flag == 1:
		ans += 1
print(ans)


def solve():
	(p, q, l, r) = map(int, input().split())
	x = []
	z_uptime = set()
	x_uptime = set()
	for _ in range(p):
		(a, b) = map(int, input().split())
		for i in range(a, b + 1):
			z_uptime.add(i)
	for _ in range(q):
		(a, b) = map(int, input().split())
		for i in range(a, b + 1):
			x_uptime.add(i)
	x_uptime = list(x_uptime)
	x_all_uptime = []
	for i in range(l, r + 1):
		tmp = [j + i for j in x_uptime]
		x_all_uptime.append(tmp)
	ans = 0
	for uptime in x_all_uptime:
		common = z_uptime.intersection(set(uptime))
		if len(common) != 0:
			ans += 1
	print(ans)
solve()


(p, q, l, r) = map(int, input().split())
a = []
b = []
for i in range(p):
	x = list(map(int, input().split()))
	a.append(x)
for i in range(q):
	x = list(map(int, input().split()))
	b.append(x)
mx = a[p - 1][1] + 1
c1 = [0] * mx
c2 = [0] * mx
j = 0
k = 0
for i in range(mx):
	if j < p:
		if i > a[j][1]:
			j += 1
	if k < q:
		if i > b[k][1]:
			k += 1
	if j < p:
		if i >= a[j][0] and i <= a[j][1]:
			c1[i] = 1
	if k < q:
		if i >= b[k][0] and i <= b[k][1]:
			c2[i] = 1
for i in range(l):
	c2.insert(0, 0)
ans = 0
for i in range(r - l + 1):
	f = 0
	for j in range(mx):
		if c1[j] + c2[j] == 2:
			f = 1
			break
	if f == 1:
		ans += 1
	c2.insert(0, 0)
print(ans)


def overlap(x, y):
	return x[1] >= y[0] and x[0] <= y[1]
line = input()
line = line.split()
p = int(line[0])
q = int(line[1])
l = int(line[2])
r = int(line[3])
z = []
for i in range(0, p):
	interval = input()
	z.append(tuple(map(int, interval.split())))
x = []
for i in range(0, q):
	interval = input()
	x.append(tuple(map(int, interval.split())))
cont = 0
for i in range(l, r + 1):
	achou = False
	for intervalX in x:
		realIntervalX = (intervalX[0] + i, intervalX[1] + i)
		for intervalZ in z:
			if overlap(realIntervalX, intervalZ):
				cont += 1
				achou = True
				break
		if achou:
			break
print(cont)


(p, q, l, r) = map(int, input().split())
z = []
dif = [i for i in range(l, r + 1)]
res = set([])
for i in range(p):
	(a, b) = map(int, input().split())
	for i in range(a, b + 1):
		z.append(i)
for i in range(q):
	(c, d) = map(int, input().split())
	toremove = []
	for (index, i) in enumerate(dif):
		st = c + i
		ft = d + i
		for a in z:
			if st <= a <= ft:
				toremove.append(i)
				res.add(i)
				break
	for t in toremove:
		dif.remove(t)
print(len(res))


(p, q, l, r) = map(int, input().split())
A = []
B = []
count = 0
f = 0
for i in range(p):
	(a, b) = map(int, input().split())
	A.append([a, b])
for i in range(q):
	(a, b) = map(int, input().split())
	B.append([a, b])
for i in range(l, r + 1):
	for j in range(q):
		(x, y) = (B[j][0] + i, B[j][1] + i)
		for k in range(p):
			(a, b) = (A[k][0], A[k][1])
			if a > y or b < x:
				continue
			else:
				f = 1
				break
		if f == 1:
			count += 1
			f = 0
			break
print(count)


(p, q, l, r) = map(int, input().split())
ek = []
dui = []
for _ in range(p):
	(a, b) = map(int, input().split())
	ek += [i for i in range(a, b + 1)]
for _ in range(q):
	(a, b) = map(int, input().split())
	dui += [i for i in range(a, b + 1)]
ans = 0
for t in range(l, r + 1):
	for i in dui:
		if i + t in ek:
			ans += 1
			break
print(ans)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
mod2 = 998244353
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def JA(a, sep):
	return sep.join(map(str, a))

def JAA(a, s, t):
	return s.join((t.join(map(str, b)) for b in a))

def IF(c, t, f):
	return t if c else f

def YES(c):
	return IF(c, 'YES', 'NO')

def Yes(c):
	return IF(c, 'Yes', 'No')

def main():
	t = 1
	rr = []
	for _ in range(t):
		(p, q, l, r) = LI()
		a = [LI() for _ in range(p)]
		b = [LI() for _ in range(q)]
		al = len(a)
		bl = len(b)

		def f(i):
			c = [[d + i, e + i] for (d, e) in b]
			t = 0
			ai = 0
			ci = 0
			while ai < al and ci < bl:
				l = max(a[ai][0], c[ci][0])
				if a[ai][1] < c[ci][1]:
					if l <= a[ai][1]:
						return 1
					ai += 1
				else:
					if l <= c[ci][1]:
						return 1
					ci += 1
			return 0
		rr.append(sum([f(i) for i in range(l, r + 1)]))
	return JA(rr, '\n')
print(main())


def main():
	from sys import stdin, stdout
	(p, q, l, r) = map(int, stdin.readline().split())
	a = []
	b = []
	visited = list((0 for x in range(r - l + 1)))
	for i in range(p):
		(x, y) = map(int, stdin.readline().split())
		a.append(x)
		b.append(y)
	for i in range(q):
		(x, y) = map(int, stdin.readline().split())
		x += l
		y += l
		for j in range(p):
			lower = max(0, a[j] - y)
			upper = min(b[j] - x, r) + 1
			if upper > lower:
				delta = upper - lower
				visited[lower:upper] = list((1 for x in range(delta)))
	stdout.write(str(visited[:r - l + 1].count(1)))
main()


(p, q, l, r) = (int(x) for x in input().split())
(tx, val) = ([], [False] * (r - l + 1))
for i in range(p):
	tx.append([int(x) for x in input().split()])
for i in range(q):
	(c, d) = (int(x) for x in input().split())
	for x in tx:
		for j in range(max(l, x[0] - d), min(r, x[1] - c) + 1):
			val[j - l] = True
print(sum(val))


def zip_sorted(a, b):
	(a, b) = zip(*sorted(zip(a, b)))
	sorted(zip(a, b), key=lambda x: x[1])
	return (a, b)
import sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
(p, q, l, r) = I()
a = [0] * p
b = [0] * p
for i in range(p):
	(a[i], b[i]) = I()
c = [0] * q
d = [0] * q
for i in range(q):
	(c[i], d[i]) = I()
cont = 0
for i in range(l, r + 1):
	count = 0
	for j in range(p):
		for k in range(q):
			if a[j] <= c[k] + i <= b[j] or a[j] <= d[k] + i <= b[j] or c[k] + i <= b[j] <= d[k] + i or (c[k] + i <= a[j] <= d[k] + i):
				count = 1
				break
		if count == 1:
			break
	if count == 1:
		cont = cont + 1
print(cont)


while True:
	try:

		def soln(l, r, z, x):
			(z_shdul, x_shdul) = (list(), [])
			for i in range(len(z)):
				(a, b) = (z[i][0], z[i][1])
				for j in range(a, b + 1, 1):
					z_shdul.append(j)
			for i in range(len(x)):
				(a, b) = (x[i][0], x[i][1])
				for j in range(a, b + 1, 1):
					x_shdul.append(j)
			tim = 0
			while l <= r:
				for xs in x_shdul:
					if xs + l in z_shdul:
						tim += 1
						break
				l += 1
			print(tim)

		def read():
			(p, q, l, r) = map(int, input().split())
			z = list()
			x = list()
			for i in range(p):
				(a, b) = map(int, input().split())
				z.append([a, b])
			for i in range(q):
				(a, b) = map(int, input().split())
				x.append([a, b])
			soln(l, r, z, x)
		if __name__ == '__main__':
			read()
	except EOFError:
		break


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
starttime = time.time()
mod = int(pow(10, 9) + 7)
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def L():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
try:
	sys.setrecursionlimit(int(pow(10, 6)))
	sys.stdin = open('input.txt', 'r')
except:
	pass
(p, q, l, r) = L()
P = []
Q = []
for i in range(p):
	P.append(L())
for i in range(q):
	Q.append(L())
B = [0 for i in range(2000)]
for ele in P:
	B[ele[0]:ele[1] + 1] = [1] * (ele[1] - ele[0] + 1)
ans = 0
for i in range(l, r + 1):
	for ele in Q:
		if 1 in B[ele[0] + i:ele[1] + i + 1]:
			ans += 1
			break
print(ans)
endtime = time.time()


(p, q, l, r) = map(int, input().split())
ps = []
qs = []
ans = []
z = [int(z) for z in range(l, r + 1)]
for i in range(p):
	(a, b) = map(int, input().split())
	for j in range(a, b + 1):
		ps.append(j)
for i in range(q):
	(a, b) = map(int, input().split())
	for j in range(a, b + 1):
		qs.append(j)
cnt = 0
for i in z:
	for var in qs:
		if var + i in ps:
			cnt += 1
			break
print(cnt)


def inter(A, B, t):
	for i in B:
		if i + t in A:
			return True
	return False
(p, q, r, l) = map(int, input().split())
X = set()
Z = set()
for i in range(p):
	(b, e) = map(int, input().split())
	for i in range(b, e + 1):
		Z.add(i)
for i in range(q):
	(b, e) = map(int, input().split())
	for i in range(b, e + 1):
		X.add(i)
cnt = 0
for i in range(r, l + 1):
	if inter(Z, X, i):
		cnt += 1
print(cnt)


(p, q, l, r) = map(int, input().split())
x = []
for i in range(p):
	x.append(list(map(int, input().split())))
z = []
for i in range(q):
	z.append(list(map(int, input().split())))
ans = 0
for i in range(l, r + 1):
	foundAns = False
	for j in range(p):
		for k in range(q):
			if x[j][1] >= z[k][0] + i >= x[j][0] or x[j][1] >= z[k][1] + i >= x[j][0] or z[k][1] + i >= x[j][0] >= z[k][0] + i or (z[k][1] + i >= x[j][1] >= z[k][0] + i):
				ans += 1
				foundAns = True
				break
		if foundAns:
			break
print(ans)


(p, q, l, r) = map(int, input().split())
n = []
m = []
for i in range(p):
	n.append(list(map(int, input().split())))
for i in range(q):
	m.append(list(map(int, input().split())))
ans = 0
z = 0
for i in range(l, r + 1):
	c = False
	for j in range(q):
		x = m[j][0] + i
		y = m[j][1] + i
		for k in range(p):
			if x <= n[k][0] and y >= n[k][0]:
				c = True
				break
			elif x > n[k][0] and x <= n[k][1]:
				c = True
				break
		if c:
			break
	if c:
		z += 1
print(z)


import pdb
import sys

def get_input_file():
	f = open('demo469.txt', 'r')
	var = f.read()
	return var

def solve():
	inp = sys.stdin.read()
	mylist = inp.splitlines()
	(p, q, l, r) = [int(elem) for elem in mylist[0].split(' ')]
	times = list()
	z_times = list()
	x_times = list()
	count = 0
	for elem in mylist[1:]:
		(first, last) = elem.split(' ')
		times.append(list(range(int(first), int(last) + 1)))
	for elem in times[0:p]:
		z_times = z_times + elem
	for elem in times[p:]:
		x_times = x_times + elem
	for i in range(l, r + 1):
		x_new = [x + i for x in x_times]
		for j in x_new:
			if j in z_times:
				count += 1
				break
	print(count)

def main():
	solve()
main()


def inp():
	return map(int, input().split())
(p, q, l, r) = inp()
(a, c, ans) = ([], [], 0)
for i in range(p + q):
	(x, y) = inp()
	if i < p:
		a.append([x, y])
	else:
		c.append([x, y])
for i in range(l, r + 1):
	flag = 0
	for j in a:
		for k in c:
			if not (k[0] + i > j[1] or k[1] + i < j[0]):
				ans += 1
				flag = 1
				break
		if flag:
			break
print(ans)


from sys import stdin, stdout
from itertools import accumulate
nmbr = lambda : int(stdin.readline())
lst = lambda : list(map(int, stdin.readline().split()))
for _ in range(1):
	(n1, n2, l1, r) = lst()
	l = [lst() for _ in range(n1)]
	a = [lst() for _ in range(n2)]
	ans = set()
	for t in range(l1, r + 1):
		for (s, e) in a:
			for (fs, fe) in l:
				if e + t < fs or fe < s + t:
					continue
				ans.add(t)
	print(len(ans))


count = 0
z = set()
x = set()
(p, q, l, r) = list(map(int, input().split(' ')))
for i in range(p):
	(a, b) = list(map(int, input().split(' ')))
	[z.add(n) for n in range(a, b + 1)]
for j in range(q):
	(c, d) = list(map(int, input().split(' ')))
	[x.add(n) for n in range(c, d + 1)]
for k in range(l, r + 1):
	for l in x:
		if l + k in z:
			count += 1
			break
print(count)


(p, q, l, r) = map(int, input().split())
a = [0] * p
b = [0] * p
c = [0] * q
d = [0] * q
e = [0] * 1001
for i in range(p):
	(a[i], b[i]) = map(int, input().split())
	for j in range(a[i], b[i] + 1):
		e[i] += 1
for i in range(q):
	(c[i], d[i]) = map(int, input().split())
n = 0
for k in range(l, r + 1):
	exist = False
	for i in range(p):
		for j in range(q):
			if max(a[i], c[j] + k) <= min(b[i], d[j] + k):
				n += 1
				exist = True
			if exist:
				break
		if exist:
			break
print(n)


import sys
import bisect
import heapq
from math import *
from collections import defaultdict as dd
from collections import deque
from collections import Counter as c
from itertools import combinations as comb
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(var):
	sys.stdout.write(var)

def l():
	return list(map(int, data().split()))

def sl():
	return list(map(str, data().split()))

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [[val for i in range(n)] for j in range(m)]
(p, q, left, right) = sp()
(x, z) = (list(), list())
for i in range(p):
	x.append(l())
for i in range(q):
	z.append(l())
answer = 0
for t in range(left, right + 1):
	overlap = set()
	for j in range(p):
		(a, b) = (x[j][0], x[j][1])
		for k in range(q):
			(c, d) = (z[k][0] + t, z[k][1] + t)
			(t1, t2) = (max(a, c), min(b, d))
			for i in range(t1, t2 + 1):
				overlap.add(i)
	if len(overlap):
		answer += 1
out(str(answer))


import sys
from functools import lru_cache

def merge(f):
	f.sort()
	if len(f) <= 1:
		return f
	for (e, interval) in enumerate(f):
		if e == len(f) - 1:
			continue
		n = f[e + 1]
		if interval[1] >= n[0]:
			f[e] = None
			f[e + 1] = (interval[0], max(interval[1], n[1]))
	return [i for i in f if i is not None]

def valid(f, s, add, i, j):
	if i >= len(f) or j >= len(s):
		return False
	f1 = f[i]
	s1 = (s[j][0] + add, s[j][1] + add)
	if s1[1] < f1[0]:
		return valid(f, s, add, i, j + 1)
	elif f1[1] < s1[0]:
		return valid(f, s, add, i + 1, j)
	else:
		return True

def main(f, s, l, r):
	f = merge(f)
	s = merge(s)
	ss = 0
	for i in range(l, r + 1):
		if valid(f, s, i, 0, 0):
			ss += 1
	print(ss)
f = []
s = []
for (e, line) in enumerate(sys.stdin.readlines()):
	inp = map(int, line.strip().split())
	if e == 0:
		(p, q, l, r) = inp
	elif p > 0:
		(a, b) = inp
		f.append((a, b))
		p -= 1
	else:
		(a, b) = inp
		s.append((a, b))
main(f, s, l, r)


(p, q, l, r) = [int(y) for y in input().split()]
x = []
for _ in range(p):
	(a, b) = [int(z) for z in input().split()]
	x.append([a, b])
y = []
for _ in range(q):
	(c, d) = [int(z) for z in input().split()]
	y.append([c, d])
x = sorted(x, key=lambda item: item[0])
y = sorted(y, key=lambda item: item[0])
cnt = 0
for i in range(l, r + 1):
	temp = [[a + i, b + i] for (a, b) in y]
	for (j1, k1) in x:
		flag = False
		for (j2, k2) in temp:
			if j2 > k1:
				break
			if not j1 > k2:
				cnt += 1
				flag = True
				break
		if flag:
			break
print(cnt)


(p, q, l, r) = map(int, input().split())
s = []
D = []
for i in range(p):
	(a, b) = map(int, input().split())
	s += [int(i) for i in range(a, b + 1)]
for i in range(q):
	(c, d) = map(int, input().split())
	D.append([c, d])
g = 0
for i in range(l, r + 1):
	p = True
	k = 0
	while p and k < q:
		ss = [int(i) for i in range(D[k][0] + i, D[k][1] + i + 1)]
		if set(s) & set(ss):
			g += 1
			p = False
			break
		else:
			k += 1
print(g)


(p, q, l, r) = map(int, input().split())
l1 = set()
l2 = set()
count = 0
for i in range(p):
	(a, b) = map(int, input().split())
	[l1.add(n) for n in range(a, b + 1)]
for i in range(q):
	(c, d) = map(int, input().split())
	[l2.add(n) for n in range(c, d + 1)]
for i in range(l, r + 1):
	for x in l2:
		if i + x in l1:
			count += 1
			break
print(count)


(n, q, l, r) = [int(i) for i in input().split()]
(arr, res) = ([], [0] * (r - l + 1))
for i in range(n):
	arr.append([int(i) for i in input().split()])
for i in range(q):
	(c, d) = [int(i) for i in input().split()]
	for x in arr:
		for j in range(max(l, x[0] - d), min(r, x[1] - c) + 1):
			res[j - l] = 1
print(sum(res))


(p, q, l, r) = map(int, input().split())
resp = [False for x in range(1001)]
Z = []
X = []
for i in range(p):
	Z.append(tuple(map(int, input().split())))
for i in range(q):
	X.append(list(map(int, input().split())))
for ls in X:
	ls[0] += l
	ls[1] += l
r -= l

def turnOn(fr, to):
	global resp
	for i in range(fr, to + 1):
		resp[i] = True

def process(vary, fixed):
	if vary[0] >= fixed[0] and vary[0] <= fixed[1] or (vary[1] >= fixed[0] and vary[1] <= fixed[1]):
		turnOn(0, min(r, fixed[1] - vary[0]))
	elif vary[1] < fixed[0]:
		if vary[1] + r >= fixed[0]:
			aux = fixed[0] - vary[1]
			turnOn(aux, min(r, aux + (fixed[1] - fixed[0] + (vary[1] - vary[0]))))
for i in X:
	for j in Z:
		process(i, j)
count = 0
for i in resp:
	if i:
		count += 1
print(count)


(p, q, l, r) = map(int, input().split())
abs = []
for i in range(p):
	abs.append(list(map(int, input().split())))
cds = []
for i in range(q):
	cds.append(list(map(int, input().split())))
shifts = [False for i in range(1001)]
for ab in abs:
	for i in range(ab[0], ab[1] + 1):
		for cd in cds:
			for j in range(cd[0], min(cd[1], i) + 1):
				shift = i - j
				if shift >= 0:
					shifts[shift] = True
sol = 0
for i in range(l, r + 1):
	if shifts[i]:
		sol += 1
print(sol)


def check(t):
	for j in range(q):
		for k in range(max(0, c[j] + t), min(1001, d[j] + t + 1)):
			if f[k]:
				return True
	return False
inp = lambda : map(int, input().split())
(p, q, l, r) = inp()
f = [False] * 1001
for i in range(p):
	(a, b) = inp()
	f = f[:a] + [True] * (b - a + 1) + f[b + 1:]
c = []
d = []
for i in range(q):
	(c1, d1) = inp()
	c.append(c1)
	d.append(d1)
ans = 0
for i in range(l, r + 1):
	if check(i):
		ans += 1
print(ans)


(p, q, l, r) = [int(x) for x in input().split()]
z = []
for i in range(p):
	z.append([int(x) for x in input().split()])
x = []
for i in range(q):
	x.append([int(xx) for xx in input().split()])
lenx = len(x)
lenz = len(z)
ans = 0
for val in range(l, r + 1):
	i = 0
	j = 0
	f = 0
	while i < lenx and j < lenz:
		x1 = x[i][0] + val
		x2 = x[i][1] + val
		if x2 < z[j][0]:
			i += 1
		elif x1 > z[j][1]:
			j += 1
		else:
			f = 1
			break
	if f == 1:
		ans += 1
print(ans)


(a, b, c, d) = map(int, input().split())
k = [*range(c, d + 1)]
e = [0] * 2001
f = [0] * 2001
for _ in ' ' * a:
	(u, v) = map(int, input().split())
	for i in range(u, 1 + v):
		e[i] = 1
for _ in ' ' * b:
	(u, v) = map(int, input().split())
	for i in range(u, 1 + v):
		f[i] = 1
ans = 0
for i in range(1001):
	if f[i]:
		x = []
		for j in k:
			if e[i + j]:
				ans += 1
				x += [j]
		for j in x:
			k.remove(j)
print(ans)


from sys import stdin
stdin.readline

def mp():
	return list(map(int, stdin.readline().strip().split()))

def it():
	return int(stdin.readline().strip())
from math import pi

def shift(S, i):
	return set((x + i for x in S))
ans = 0
(p, q, l, r) = mp()
(pp, qq) = (set(), set())
for i in range(p):
	(a, b) = mp()
	pp.update(range(a, b + 1))
for i in range(q):
	(a, b) = mp()
	qq.update(range(a, b + 1))
for i in range(l, r + 1):
	if shift(qq, i) & pp:
		ans += 1
print(ans)


(p, q, l, r) = map(int, input().split())
Z = [tuple(map(int, input().split())) for _ in range(p)]
X = [tuple(map(int, input().split())) for _ in range(q)]
total = set()
for (a, b) in Z:
	for (c, d) in X:
		diff = d - c + 1
		x = a - c + 1
		st = max(l, x - diff)
		en = min(r, b - c)
		for i in range(st, en + 1):
			total.add(i)
print(len(total))


(p, q, l, r) = list(map(int, input().split(' ')))
P = []
Q = []
for i in range(p):
	P.append(list(map(int, input().split(' '))))
for i in range(q):
	Q.append(list(map(int, input().split(' '))))
res = 0
for i in range(l, r + 1):
	index_q = 0
	index_p = 0
	for j in range(p + q):
		if index_q == q or index_p == p:
			break
		if P[index_p][1] < Q[index_q][0] + i:
			index_p += 1
		elif Q[index_q][1] + i < P[index_p][0]:
			index_q += 1
		else:
			res += 1
			break
print(res)


from collections import defaultdict, deque, Counter, OrderedDict
from math import gcd

def main():
	(p, q, l, r) = map(int, input().split())
	z = [tuple(map(int, input().split())) for i in range(p)]
	x = [tuple(map(int, input().split())) for i in range(q)]
	ans = 0
	for shift in range(l, r + 1):
		check = False
		for i in x:
			if check:
				break
			i = (i[0] + shift, i[1] + shift)
			for j in z:
				if not (i[1] < j[0] or j[1] < i[0]):
					ans += 1
					check = True
					break
	print(ans)
main()


(p, q, l, r) = map(int, input().split())
x_availabilities = [tuple(map(int, input().split())) for _ in range(p)]
y_availabilities = [tuple(map(int, input().split())) for _ in range(q)]

def has_shared_moments(x, y):
	for i in x:
		for j in y:
			if i[0] <= j[1] and j[0] <= i[1]:
				return True
count = 0
for i in range(l, r + 1):
	if has_shared_moments(x_availabilities, [(x[0] + i, x[1] + i) for x in y_availabilities]):
		count += 1
print(count)


__author__ = 'sonerik'
import sys
inp = sys.stdin
(p, q, l, r) = map(int, inp.readline().strip().split())
(z, x) = ([], [])
for i in range(p):
	(a_i, b_i) = map(int, inp.readline().strip().split())
	z += [i for i in range(a_i, b_i + 1)]
z_set = set(z)
for i in range(q):
	(c_i, d_i) = map(int, inp.readline().strip().split())
	x += [i for i in range(c_i, d_i + 1)]
cnt = 0
for i in range(l, r + 1):
	new_x = [j + i for j in x]
	new_x_set = set(new_x)
	if new_x_set.intersection(z_set):
		cnt += 1
print(cnt)


(p, q, l, r) = map(int, input().split())
z = set()
for i in range(p):
	(a, b) = map(int, input().split())
	z.update([x for x in range(a, b + 1)])
x = []
for i in range(q):
	(a, b) = map(int, input().split())
	x += [e for e in range(a, b + 1)]
res = 0
for i in range(l, r + 1):
	for j in x:
		if j + i in z:
			res += 1
			break
print(res)


(p, q, l, r) = map(int, input().split())
mySet1 = set()
mySet2 = set()
for i in range(p):
	(a, b) = map(int, input().split())
	for i in range(a, b + 1):
		mySet1.add(i)
for i in range(q):
	(a, b) = map(int, input().split())
	for i in range(a, b + 1):
		mySet2.add(i)
m = max(mySet1)
cnt = 0
for t in range(l, r + 1):
	for item in mySet2:
		if t + item in mySet1:
			cnt += 1
			break
print(cnt)


(p, q, l, r) = map(int, input().split())
t1 = []
for _ in range(p):
	(x, y) = map(int, input().split())
	t1.append([x, y])
t2 = []
for _ in range(q):
	(x, y) = map(int, input().split())
	t2.append([x, y])
ans = 0
for d in range(l, r + 1):
	s = 0
	(i1, i2) = (0, 0)
	while i1 < p and i2 < q:
		if t1[i1][0] > t2[i2][1] + d:
			i2 += 1
		elif t1[i1][1] < t2[i2][0] + d:
			i1 += 1
		else:
			s = 1
			break
	if s:
		ans += 1
print(ans)


(p, q, l, r) = map(int, input().split())
Z = []
X = []
while p:
	Z.append(list(map(int, input().split())))
	p -= 1
while q:
	X.append(list(map(int, input().split())))
	q -= 1
Z.sort()
X.sort()
overlap = 0
while l <= r:
	for value in Z:
		flag = False
		for values in X:
			start = values[0] + l
			end = values[1] + l
			if start > value[1]:
				break
			if not value[0] > end:
				overlap += 1
				flag = True
				break
		if flag:
			break
	l += 1
print(overlap)


import math

def increase(arr, val):
	for i in range(len(arr)):
		arr[i][0] += val
		arr[i][1] += val
	return arr

def main(tmie1, time2, l, r):
	ans = 0
	for i in range(l, r + 1):
		if i == l:
			time2 = increase(time2, l)
		else:
			time2 = increase(time2, 1)
		found = False
		for e1 in time1:
			for e2 in time2:
				(x1, y1) = e1
				(x2, y2) = e2
				if x1 > x2:
					(x1, y1) = e2
					(x2, y2) = e1
				if x2 <= y1:
					found = True
		if found:
			ans += 1
	return ans
(p, q, l, r) = list(map(int, input().split()))
time1 = []
time2 = []
for i in range(p):
	time1.append(list(map(int, input().split())))
for i in range(q):
	time2.append(list(map(int, input().split())))
print(main(time1, time2, l, r))


import os
import re
import sys
from bisect import bisect, bisect_left, insort, insort_left
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from io import BytesIO, IOBase
from itertools import accumulate, combinations, combinations_with_replacement, groupby, permutations, product
from math import acos, asin, atan, ceil, cos, degrees, factorial, hypot, log2, pi, radians, sin, sqrt, tan
from operator import itemgetter, mul
from string import ascii_lowercase, ascii_uppercase, digits

def inp():
	return int(input())

def inlist():
	return list(map(int, input().split()))

def instr():
	s = input()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')
(p, q, l, r) = invr()
z = []
x = []
for _ in range(p):
	z.append(inlist())
for _ in range(q):
	x.append(inlist())
res = 0
for shift in range(l, r + 1):
	for xTime in x:
		lx = xTime[0] + shift
		rx = xTime[1] + shift
		flag = False
		for zTime in z:
			lz = zTime[0]
			rz = zTime[1]
			if rx >= lz and lx <= rz:
				res += 1
				flag = True
				break
		if flag:
			break
print(res)


import atexit
import io
import sys
_OUTPUT_BUFFER = io.StringIO()
sys.stdout = _OUTPUT_BUFFER

@atexit.register
def write():
	sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())

def interval_overlap(l1, r1, l2, r2):
	return l2 <= l1 <= r2 or l2 <= r1 <= r2 or l1 <= l2 <= r1 or (l1 <= r2 <= r1)
(p, q, l, r) = map(int, input().strip().split())
little_Z = [tuple(map(int, input().strip().split())) for _ in range(p)]
little_X = [tuple(map(int, input().strip().split())) for _ in range(q)]
will_chat = 0
for time in range(l, r + 1):
	can_chat = False
	for window_X in little_X:
		for window_Z in little_Z:
			if interval_overlap(window_Z[0], window_Z[1], window_X[0] + time, window_X[1] + time):
				can_chat = True
				break
		if can_chat:
			break
	if can_chat:
		will_chat += 1
print(will_chat)


(p, q, l, r) = map(int, input().split())
x = []
y = []
for i in range(p):
	(u, v) = map(int, input().split())
	x.extend((i for i in range(u, v + 1)))
for i in range(q):
	(u, v) = map(int, input().split())
	y.extend((i for i in range(u, v + 1)))
x = set(x)
y = set(y)
ans = 0
for i in range(l, r + 1):
	for j in y:
		if j + i in x:
			ans += 1
			break
print(ans)


N = 1001
seqAB = [False] * N
seqCD = [False] * N

def solve(p, q, l, r, a, b, c, d):
	for (x, y) in zip(a, b):
		for i in range(x, y + 1):
			seqAB[i] = True
	for (x, y) in zip(c, d):
		for i in range(x, y + 1):
			seqCD[i] = True
	ans = 0
	for i in range(l, r + 1):
		for j in range(i, N):
			if seqAB[j] and seqCD[j - i]:
				ans += 1
				break
	return ans

def read():
	return [int(c) for c in input().split()]

def main():
	(p, q, l, r) = read()
	(a, b, c, d) = ([], [], [], [])
	for _ in range(p):
		(x, y) = read()
		a.append(x)
		b.append(y)
	for _ in range(q):
		(x, y) = read()
		c.append(x)
		d.append(y)
	ans = solve(p, q, l, r, a, b, c, d)
	print(ans)
main()


import sys
INT_MAX = sys.maxsize
INT_MIN = -sys.maxsize - 1
sys.setrecursionlimit(10 ** 7)
mod = 1000000007

def IOE():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def main():
	(p, q, l, r) = map(int, sys.stdin.readline().split())
	z = [0] * 1502
	c = 0
	xtime = []
	for i in range(p):
		(a, b) = map(int, sys.stdin.readline().split())
		for j in range(a, b + 1):
			z[j] = 1
	for i in range(q):
		(f, s) = map(int, sys.stdin.readline().split())
		xtime.append([f, s])
	for t in range(l, r + 1):
		for i in range(q):
			(x, y) = (xtime[i][0] + t, xtime[i][1] + t)
			if z[x:y + 1].count(1):
				c += 1
				break
	print(c)
try:
	IOE()
except:
	pass
main()


import sys
from bisect import *
INF = 1000000000.0
Input = []
MOD = 1000000007

def Out(x):
	sys.stdout.write(str(x) + '\n')

def In():
	return sys.stdin.readline().strip().split()

def inputGrab():
	for line in sys.stdin:
		Input.extend(map(str, line.strip().split()))

def main():
	(p, q, l, r) = map(int, In())
	point = [0 for i in range(1010)]
	for i in range(p):
		(x, y) = map(int, In())
		for j in range(x, y + 1):
			point[j] += 1
	ans = 0
	donePoints = {}
	for i in range(q):
		(x, y) = map(int, In())
		for j in range(l, r + 1):
			if j in donePoints:
				continue
			for k in range(x + j, min(y + j + 1, 1001)):
				if point[k]:
					ans += 1
					donePoints[j] = True
					break
	print(ans)
main()


(p, q, l, r) = list(map(int, input().split()))
z = []
for i in range(p):
	z.append(list(map(int, input().split())))
x = []
for i in range(q):
	x.append(list(map(int, input().split())))
s = set()
for i in range(p):
	for j in range(q):
		if x[j][0] + l > z[i][1] or x[j][1] + r < z[i][0]:
			continue
		min_s = z[i][0] - x[j][1] if x[j][1] + l < z[i][0] else l
		max_s = min(z[i][1] - x[j][0], r)
		s.update(range(min_s, max_s + 1))
		if len(s) == r - l + 1:
			print(len(s))
			exit()
print(len(s))


def mingrid():
	for _ in range(int(input())):
		n = int(input())
		segcost = input().split()
		minodd = int(segcost[0])
		mineven = int(segcost[1])
		sumodd = minodd
		sumeven = mineven
		codd = 1
		ceven = 1
		res = sumodd + minodd * (n - codd) + sumeven + mineven * (n - ceven)
		for i in range(2, n):
			now = int(segcost[i])
			if (i + 1) % 2:
				minodd = min(minodd, now)
				sumodd += now
				codd += 1
			else:
				mineven = min(mineven, now)
				sumeven += now
				ceven += 1
			res = min(res, sumodd + minodd * (n - codd) + sumeven + mineven * (n - ceven))
		print(res)

def numofpairs():
	n = (10 * 2) ** 7 + 1
	l = [False] * n
	primes = []
	for i in range(2, n):
		if not l[i]:
			for i1 in range(i + i, n, i):
				l[i1] = True
			primes.append(i)
			l[i] = True
	tol = [0, 0]
	for i in range(2, n):
		pos = 0
		t = 0
		while i:
			val = primes[pos]
			if not i:
				tol.append(t)
				break
			elif i < val:
				tol.append(t + 1)
				break
			elif not i % val:
				i //= val
			else:
				pos += 1
				t += 1
	for _ in range(int(input())):
		(c, d, x) = map(int, input().split())
		lim = int(math.sqrt(x)) + 1
		ans = 0
		for i in range(1, lim):
			thing = i + d
			if thing % c:
				continue
			ans += 2 ** tol[thing // c]
		print(ans)

def restoremod():
	for _ in range(int(input())):
		length = int(input()) - 1
		l = input().split()
		t = False
		ife = False
		for i in range(length):
			if int(l[i]) == int(l[i + 1]):
				if i > 0:
					print(-1)
					t = True
					break
				else:
					ife = True
			elif ife:
				print(-1)
				t = True
				break
		if not t:
			posc = 0
			negc = 0
			res = int(l[1]) - int(l[0])
			if res > 0:
				posc = res
			else:
				negc = res
			if not negc:
				for i in range(1, length):
					now = int(l[i]) - int(l[i + 1])
					if now > 0:
						negc = now
						break
			if not posc:
				for i in range(1, length):
					change = int(l[i + 1]) - int(l[i])
					if change > 0:
						posc = change
						break
			if posc and negc:
				mod = posc + negc
			else:
				mod = 0
			c = posc if posc else -negc
			larnum = 0
			for i in range(length):
				nowi = int(l[i])
				larnum = max(larnum, nowi)
				if larnum > mod and mod:
					print(-1)
					t = True
					break
				res = int(l[i + 1]) - nowi
				if res < 0:
					if res != -(mod - c):
						print(-1)
						t = True
						break
				if res > 0:
					if res != c:
						t = True
						print(-1)
						break
			if not t:
				if mod:
					print(mod, c, sep=' ')
				else:
					print(mod)

def restoremod1():
	for _ in range(int(input())):
		num = int(input())
		...

def cells():
	for _ in range(int(input())):
		(row, col, num) = map(int, input().split())
		nr = (num - 1) % row
		nc = (num - 1) // row + 1
		print(nr * col + nc)

def replacement():
	for _ in range(int(input())):
		(l, k) = map(int, input().split())
		s = input()
		(left, righ) = (s.find('*'), s.rfind('*'))
		if righ - left <= k:
			print(2 if righ != left else 1)
		else:
			pos = left
			c = 2
			while righ - pos > k:
				pos = pos + k
				while pos < l and s[pos] != '*':
					pos -= 1
				c += 1
			print(c)
import math
import sys
input = sys.stdin.readline

def string():
	for _ in range(int(input())):
		s = input().rstrip()
		s1 = input().rstrip()
		maxl = 0
		p1 = [0, 0]
		p = [0, 0]
		for i in range(len(s)):
			for i1 in range(i + 1, len(s) + 1):
				pos = s1.find(s[i:i1])
				if pos == -1:
					break
				elif i1 - i <= maxl:
					continue
				elif i1 - i > maxl:
					maxl = i1 - i
					p1 = [pos, pos + maxl]
					p = [i, i + maxl]
		print(p[0] + len(s) - p[1] + (p1[0] + len(s1) - p1[1]) if maxl else len(s) + len(s1))
import collections

def trans(l):
	pos = 0
	while pos < len(l) - 1:
		avg = l[pos] // (len(l) - pos - 1)
		rem = l[pos] % (len(l) - pos - 1)
		l[pos] = 0
		for i in range(pos + 1, len(l)):
			l[i] -= avg
			if l[i] < 0:
				rem += -l[i]
				l[i] = 0
		while pos + 1 < len(l) and l[pos + 1] <= rem:
			rem -= l.pop(pos + 1)
		if pos + 1 < len(l):
			l[pos + 1] -= rem
		else:
			l[0] = rem
		pos += 1
	return sum(l)

def trans1(l):
	pos = 0
	lenl = len(l)
	pos1 = pos + 1
	while pos1 < lenl and pos < lenl:
		while pos1 < lenl and l[pos] - l[pos1] >= 0:
			l[pos] -= l[pos1]
			l[pos1] = 0
			pos1 += 1
		if pos1 < lenl:
			l[pos1] -= l[pos]
			l[pos] = 0
			pos = pos1
			pos1 += 1
	return sum(l)

def main():
	for _ in range(int(input())):
		num = input()
		l = sorted(list(collections.Counter(input().split()).values()), reverse=True)
		ans = trans(l[:])
		if ans:
			print(min(ans, trans1(l)))
		else:
			print(0)

def transrep():
	for _ in range(int(input())):
		num = int(input())
		l = list(collections.Counter(input().split()).values())
		ml = max(l)
		if ml > num - ml:
			print(ml - num + ml)
		else:
			print(num % 2)

def resmod():

	def solve():
		posc = -1
		negc = 1
		num = int(input())
		l = input().split()
		ifz = False
		maxi = int(l[0])
		for i in range(num - 1):
			maxi = max(maxi, int(l[i + 1]))
			c = int(l[i + 1]) - int(l[i])
			if c == 0:
				if not i:
					ifz = True
					continue
				elif not ifz:
					return -1
			elif ifz:
				return -1
			elif c < 0:
				if negc == 1:
					negc = c
				elif negc != c:
					return -1
			elif c > 0:
				if posc == -1:
					posc = c
				elif posc != c:
					return -1
		if posc == -1 or negc == 1:
			return 0
		mod = posc + -negc
		if mod <= maxi:
			return -1
		return '{0} {1}'.format(mod, posc)
	for _ in range(int(input())):
		print(solve())

def basicdep():

	def findmax(l):
		ans = 0
		res = 0
		for (i, v) in enumerate(l):
			if ans < v:
				res = i
				ans = v
		return [res + 1, ans]

	def roundup(num):
		s = num / 2
		if s != int(s):
			return int(s) + 1
		return int(s)
	for _ in range(int(input())):
		days = []
		(f, d) = map(int, input().split())
		friends = [0] * f
		for i in range(d):
			nowfs = input().split()
			nowff = int(nowfs[1])
			friends[nowff - 1] += 1
			if int(nowfs[0]) > 1:
				days.append([nowff, int(nowfs[2])])
			else:
				days.append([nowff, []])
		maxl = findmax(friends)
		goal = roundup(d)
		if maxl[1] < goal:
			print('YES')
			print(*[i[0] for i in days], sep=' ')
		else:
			pos = 0
			while pos < d and maxl[1] > goal:
				if days[pos][0] == maxl[0] and days[pos][1]:
					days[pos][0] = days[pos][1]
					maxl[1] -= 1
				pos += 1
			if maxl[1] > goal:
				print('NO')
			else:
				print('YES')
				print(*[i[0] for i in days], sep=' ')

def playlist():

	def nextsong(pos):
		while pos + 1 in ans and len(ans) != num:
			pos += 1
			if pos == num:
				pos = 0
		return pos

	def gcf(n, n1):
		if not n:
			return n1
		return gcf(n1, n % n1) if n1 else n
	for _ in range(int(input())):
		num = int(input())
		l = input().split()
		deletel = collections.deque()
		for i in range(num - 1):
			(a, b) = (int(l[i]), int(l[i + 1]))
			if gcf(a, b) == 1:
				deletel.append((i, i + 1))
		if gcf(int(l[-1]), int(l[0])) == 1:
			deletel.append((num - 1, 0))
		ans = dict()
		while deletel and len(ans) != num:
			(a, b) = deletel.popleft()
			if a + 1 in ans or b + 1 in ans:
				continue
			ans[b + 1] = True
			if deletel:
				if deletel[0][0] == b:
					deletel.popleft()
			if b == num - 1:
				n = nextsong(0)
				if gcf(int(l[a]), int(l[n])) == 1:
					deletel.append((a, n))
			else:
				n = nextsong(b + 1)
				if gcf(int(l[a]), int(l[n])) == 1:
					deletel.append((a, n))
		print(len(ans), *ans.keys(), sep=' ')

def shoesandst():
	(students, laces) = map(int, input().split())
	d = collections.defaultdict(list)
	rems = set()
	for _ in range(laces):
		(a, b) = map(int, input().split())
		d[a].append(b)
		d[b].append(a)
		lisa = d[a]
		lisb = d[b]
		la = len(lisa)
		lb = len(lisb)
		if la == 2:
			rems.discard((a, lisa[0]))
		elif la == 1:
			rems.add((a, b))
		if lb == 2:
			rems.discard((b, lisb[0]))
		elif lb == 1:
			rems.add((b, a))
	c = 0
	nextans = set()
	while rems or nextans:
		nextans.clear()
		while rems:
			(a, b) = rems.pop()
			nextans.discard((a, b))
			nextans.discard((b, a))
			d[a].pop()
			d[b].remove(a)
			lb = len(d[b])
			if not lb:
				rems.discard((b, a))
			if lb == 1:
				nextans.add((b, d[b][0]))
		rems = nextans.copy()
		c += 1
	return c
import heapq

def restoreperm():
	for _ in range(int(input())):
		length = int(input())
		maxselect = []
		minselect = []
		ansma = []
		ansmi = []
		last = 0
		for i in input().split():
			i = int(i)
			if i == last:
				ansma.append(-heapq.heappop(maxselect))
				ansmi.append(heapq.heappop(minselect))
			else:
				ansma.append(i)
				ansmi.append(i)
				for num in range(last + 1, i):
					heapq.heappush(maxselect, -num)
					heapq.heappush(minselect, num)
				last = i
		print(*ansmi, sep=' ')
		print(*ansma, sep=' ')

def maxthestring():

	def check(l):
		return tcharacters.issubset(l)
	for _ in range(int(input())):
		s = input().rstrip()
		tcharacters = set(s)
		lsc = len(tcharacters)
		t = ''
		ts = set()
		remainings = collections.deque(s)
		while len(t) < lsc:
			maxc = ''
			for i in range(len(remainings)):
				charac = remainings.popleft()
				if maxc < charac and charac not in ts:
					maxn = remainings.copy()
					maxc = charac
				if check(remainings):
					continue
				t += maxc
				ts.add(maxc)
				break
			remainings = maxn
			tcharacters.discard(maxc)
		print(t)

def maxthestring2():

	def filout(letter, s):
		iff = False
		ans = ''
		for i in s:
			if i != letter and iff:
				ans += i
			elif i == letter:
				iff = True
		return ans
	for _ in range(int(input())):
		s = input().rstrip()
		tcharacters = set(s)
		lsc = len(tcharacters)
		ans = ''
		while lsc:
			maxc = ''
			for i in tcharacters:
				news = filout(i, s)
				if len(set(news)) == lsc - 1 and maxc < i:
					maxc = i
					save = news
			tcharacters.discard(maxc)
			ans += maxc
			s = save
			lsc -= 1
		print(ans)

def maxthestring3():
	for _ in range(int(input())):
		s = input().rstrip()
		lastpos = {v: i for (i, v) in enumerate(s)}
		queue = []
		his = set()
		for i in range(len(s)):
			nowl = s[i]
			if nowl not in his:
				if queue:
					while queue[-1] < nowl and lastpos[queue[-1]] > i:
						his.discard(queue.pop())
						if not queue:
							break
					queue.append(nowl)
					his.add(nowl)
				else:
					queue.append(nowl)
					his.add(nowl)
		print(''.join(queue))

def gcdsum():

	def calc(num):
		dsum = 0
		for i in str(nownum):
			dsum += int(i)
		return dsum

	def gcd(a, b):
		if not a:
			return b
		if not b:
			return a
		return gcd(b, a % b)
	for _ in range(int(input())):
		nownum = int(input())
		dsum = calc(nownum)
		while gcd(dsum, nownum) == 1:
			nownum += 1
			dsum = calc(nownum)
		print(nownum)

def fitbox():
	for _ in range(int(input())):
		(bnum, wid) = map(int, input().split())
		boxes = sorted(list(collections.Counter(input().split()).items()), key=lambda x: int(x[0]), reverse=True)
		ans = 0
		while bnum:
			nwid = wid
			for i in range(len(boxes)):
				boxes[i] = list(boxes[i])
				(w, c) = boxes[i]
				w = int(w)
				while nwid - w >= 0 and c:
					nwid -= w
					c -= 1
					bnum -= 1
				boxes[i][1] = c
			ans += 1
		print(ans)
import sys
sys.setrecursionlimit(10000)

def reflect():

	def recur(cur, plane, dir):
		if cur == 1:
			return 1
		now = l[cur][plane][dir]
		if now != -1:
			return now
		ans = 2
		if dir:
			if cur > 1 and plane > 1:
				ans += recur(cur - 1, plane - 1, 0) - 1
			ans %= num
			if plane < planes:
				ans += recur(cur, plane + 1, 1) - 1
			ans %= num
		else:
			if cur > 1 and plane < planes:
				ans += recur(cur - 1, plane + 1, 1) - 1
			ans %= num
			if plane > 1:
				ans += recur(cur, plane - 1, 0) - 1
			ans %= num
		l[cur][plane][dir] = ans
		return ans
	num = int(1000000000.0 + 7)
	for _ in range(int(input())):
		(planes, begin) = map(int, input().split())
		l = [[[-1] * 2 for _ in range(planes + 1)] for _ in range(begin + 1)]
		print(recur(begin, 1, 1) % num)
mod = int(1000000000.0 + 7)

def iter_solver(N, K):
	dp = [[[-1 for _ in range(2)] for __ in range(K + 1)] for ___ in range(N + 1)]
	for i in range(1, N + 1):
		dp[i][1][0] = dp[i][1][1] = 1
	for k in range(2, K + 1):
		for n in range(N, 0, -1):
			ans = 2
			if n < N:
				ans += dp[n + 1][k][0] - 1
				ans %= mod
			if n > 1:
				ans += dp[n - 1][k - 1][1] - 1
				ans %= mod
			dp[n][k][0] = ans
		for n in range(1, N + 1):
			ans = 2
			if n < N:
				ans += dp[n + 1][k - 1][0] - 1
				ans %= mod
			if n > 1:
				ans += dp[n - 1][k][1] - 1
				ans %= mod
			dp[n][k][1] = ans
	return dp[1][K][0]

def dejavu():
	for _ in range(int(input())):
		s = input().rstrip()
		l = len(s)
		temp = s + 'a'
		if temp[::-1] != temp:
			print('YES')
			print(temp)
			continue
		if l == 1:
			if s == 'a':
				print('NO')
			else:
				print('YES')
				print(s + 'a')
			continue
		for i in range(l - 1, l // 2 - 1, -1):
			d = l - i
			if s[d] != 'a':
				print('YES')
				print(s[:i] + 'a' + s[i:])
				break
		else:
			print('NO')

def bits():
	for _ in range(int(input())):
		num = int(input())
		a = [i for i in input()]
		c1 = a.count('1')
		b = input()
		for i in range(num - 1, -1, -1):
			if a[i] != b[i]:
				if c1 != i + 1 - c1:
					print('NO')
					break
				for i1 in range(i, -1, -1):
					if a[i1] == '1':
						a[i1] = '0'
					else:
						a[i1] = '1'
			if a[i] == '1':
				c1 -= 1
		else:
			print('YES')

def bitsrec():

	def tran(s, num):
		if num % 2:
			if s == '1':
				return '0'
			return '1'
		return s
	for _ in range(int(input())):
		num = int(input())
		a = input()
		b = input()
		flips = 0
		ones = a.count('1')
		for i in range(num - 1, -1, -1):
			if tran(a[i], flips) != b[i]:
				if ones != i - ones + 1:
					print('NO')
					break
				flips += 1
			if tran(a[i], flips) == '1':
				ones -= 1
		else:
			print('YES')

def balance():
	for _ in range(int(input())):
		l = int(input())
		s = input()
		ans = ''
		ans1 = ''
		open = 0
		for i in range(l):
			if not i % 2:
				ans += '('
				if s[i] == '0':
					ans1 += ')'
					open -= 1
				else:
					ans1 += '('
					open += 1
			else:
				ans += ')'
				if s[i] == '0':
					ans1 += '('
					open += 1
				else:
					ans1 += ')'
					open -= 1
			if open < 0:
				print('NO')
				break
		else:
			if not open:
				print('YES')
				print(ans)
				print(ans1)
			else:
				print('NO')

def balanceres():
	for _ in range(int(input())):
		num = int(input())
		s = [i for i in input().rstrip()]
		ones = 0
		ol = []
		zl = []
		for i in range(len(s)):
			if s[i] == '1':
				ones += 1
				ol.append(i)
			else:
				zl.append(i)
		zeros = num - ones
		if zeros % 2 or ones % 2 or s[0] == '0' or (s[-1] == '0'):
			print('NO')
		else:
			pl = ones // 2
			for i in range(ones):
				if i >= pl:
					s[ol[i]] = ')'
				else:
					s[ol[i]] = '('
			diffans = s[:]
			for i in range(zeros):
				p = zl[i]
				if i % 2:
					diffans[p] = '('
					s[p] = ')'
				else:
					diffans[p] = ')'
					s[p] = '('
			print('YES')
			print(*s, sep='')
			print(*diffans, sep='')
import sys

def coloring():
	n = int(input())
	blacks = set()
	whites = set()
	for i1 in range(n):
		for i in range(n):
			if (i + i1) % 2:
				blacks.add((i1 + 1, i + 1))
			else:
				whites.add((i1 + 1, i + 1))
	for i in range(n * n):
		colortochoose = int(input())
		if colortochoose == 1:
			if blacks:
				print(2, *blacks.pop())
			else:
				print(3, *whites.pop())
		elif colortochoose == 2:
			if whites:
				print(1, *whites.pop())
			else:
				print(3, *blacks.pop())
		elif whites:
			print(1, *whites.pop())
		else:
			print(2, *blacks.pop())
		sys.stdout.flush()

def isratedans():
	while True:
		try:
			q = input()
		except EOFError:
			break
		print('NO')
		sys.stdout.flush()

def reflectres():
	for _ in range(int(input())):
		(planes, energy) = map(int, input().split())
		count = [1] * planes
		ans = 1
		energy -= 1
		dir = 1
		while energy:
			if dir:
				cur = 0
				for i in range(planes - 1, -1, -1):
					temp = cur
					cur = (cur + count[i]) % mod
					count[i] = temp
			else:
				cur = 0
				for i in range(planes):
					temp = cur
					cur = cur + count[i] % mod
					count[i] = temp
			ans = (ans + cur) % mod
			dir = 1 - dir
			energy -= 1
		print(ans)

def possible():
	s = input().rstrip()
	compare = 0
	for i in s:
		if i == '+':
			compare += 1
		else:
			compare -= 1
	s1 = input()
	todo = [(0, 0)]
	totc = 0
	ans = 0
	while todo:
		(c, pos) = todo.pop()
		if pos >= len(s):
			totc += 1
			if compare == c:
				ans += 1
			continue
		if s1[pos] == '?':
			todo.append((c + 1, pos + 1))
			todo.append((c - 1, pos + 1))
		elif s1[pos] == '+':
			todo.append((c + 1, pos + 1))
		elif s1[pos] == '-':
			todo.append((c - 1, pos + 1))
	print(ans / totc)

def chat_online():
	(p, q, start, end) = map(int, input().split())
	pl = [list(map(int, input().split())) for _ in range(p)][::-1]
	counter = [False] * 2000
	for _ in range(q):
		now = list(map(int, input().split()))
		for i in pl:
			if i[0] >= now[0]:
				pos = max(0, i[0] - now[1])
				length = i[1] - i[0] + (now[1] - now[0])
				for i2 in range(pos, length + pos + 1):
					counter[i2] = True
			else:
				break
	c = 0
	for i in range(start, end + 1):
		if counter[i]:
			c += 1
	return c

def chatonline2():

	def check(l1, l):
		for (x, y) in l:
			(x, y) = (x + i, y + i)
			for (x1, y1) in l1:
				if x <= x1 <= y or x1 <= x <= y1:
					return True
	(p, q, start, end) = map(int, input().split())
	(l, l1) = ([list(map(int, input().split())) for _ in range(p)], [list(map(int, input().split())) for _ in range(q)])
	c = 0
	for i in range(start, end + 1):
		if check(l, l1):
			c += 1
	return c
print(chatonline2())


(p, q, l, r) = map(int, input().split())
little_x = []
little_z = []
cnt = 0
a = True
for i in range(p):
	little_z += [list(map(int, input().split()))]
for i in range(q):
	little_x += [list(map(int, input().split()))]
for t in range(l, r + 1):
	a = True
	for x in range(q):
		for z in range(p):
			if little_x[x][0] + t <= little_z[z][1] and little_x[x][1] + t >= little_z[z][0] and a:
				cnt += 1
				a = False
print(cnt)


import os
import sys
from io import BytesIO, IOBase

def main():
	(p, q, l, r) = map(int, input().split())
	z = [-2] * 1001
	for i in range(p):
		(x, y) = map(int, input().split())
		for i in range(x, y + 1):
			z[i] = 1
	ans = [0] * 1001
	for i in range(q):
		(x, y) = map(int, input().split())
		for i in range(x, y + 1):
			if z[i] == 1:
				z[i] = 0
			else:
				z[i] = -1
	for i in range(1001):
		if z[i] == -1 or z[i] == 0:
			for j in range(i + l, min(1001, i + r + 1)):
				if z[j] == 1 or z[j] == 0:
					ans[j - i] = 1
	print(sum(ans))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


(p, q, l, r) = input().split()
fixed = []
for i in range(int(p)):
	endpoints = input().split()
	for j in range(int(endpoints[0]), int(endpoints[1]) + 1):
		fixed += [j]
temp = []
for i in range(int(q)):
	endpoints = input().split()
	for j in range(int(endpoints[0]), int(endpoints[1]) + 1):
		temp += [j]
count = 0
for time in range(int(l), int(r) + 1):
	new_temp = temp[:]
	new_temp = [i + time for i in new_temp]
	for i in new_temp:
		if i in fixed:
			count += 1
			break
print(count)


(p, q, l, r) = [int(i) for i in input().split()]
cnt = 0
Z = []
X = []
for i in range(p):
	Z.append([int(i) for i in input().split()])
for i in range(q):
	X.append([int(i) for i in input().split()])
for t in range(l, r + 1):
	b = False
	for i in Z:
		for j in X:
			if i[0] <= j[0] + t <= i[1] or i[0] <= j[1] + t <= i[1] or j[0] + t <= i[0] <= j[1] + t or (j[0] + t <= i[1] <= j[1] + t):
				b = True
				break
		if b:
			cnt += 1
			break
print(cnt)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def main():
	pass

def binary(n):
	return bin(n).replace('0b', '')

def decimal(s):
	return int(s, 2)

def pow2(n):
	p = 0
	while n > 1:
		n //= 2
		p += 1
	return p

def isPrime(n):
	if n == 1:
		return False
	else:
		root = int(n ** 0.5)
		root += 1
		for i in range(2, root):
			if n % i == 0:
				return False
		return True

def lts(l):
	s = ''.join(map(str, l))
	return s

def stl(s):
	l = list(s)
	return l

def sq(a, target, arr=[]):
	s = sum(arr)
	if s == target:
		return arr
	if s >= target:
		return
	for i in range(len(a)):
		n = a[i]
		remaining = a[i + 1:]
		ans = sq(remaining, target, arr + [n])
		if ans:
			return ans

def SieveOfEratosthenes(n):
	cnt = 0
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			cnt += 1
	return cnt

def nCr(n, r):
	f = math.factorial
	return f(n) // f(r) // f(n - r)
mod = int(1000000000.0) + 7

def ssinp():
	return input()

def iinp():
	return int(input())

def nninp():
	return map(int, input().split())

def llinp():
	return list(map(int, input().split()))

def p(xyz):
	print(xyz)

def p2(a, b):
	print(a, b)
import math
from collections import OrderedDict
(x, y, r, l) = nninp()
time1 = []
time2 = []
for i in range(x):
	(a, b) = nninp()
	for j in range(a, b + 1):
		time1.append(j)
for i in range(y):
	(c, d) = nninp()
	for j in range(c, d + 1):
		time2.append(j)
ans = 0
for t in range(r, l + 1):
	temp = list(map(lambda x: x + t, time2))
	for c in temp:
		if c in time1:
			ans += 1
			break
p(ans)


import sys

def ints_input():
	return [int(i) for i in sys.stdin.readline().strip('\n').split(' ')]

def print_list(arr):
	sys.stdout.writelines((str(x) + ' ' for x in arr))
	sys.stdout.write('\n')

def fast_input(type=str):
	return type(sys.stdin.readline().strip('\n'))
(p, q, l, r) = ints_input()
(x, z) = ([], [])
for i in range(p):
	z.append(tuple(ints_input()))
for i in range(q):
	x.append(tuple(ints_input()))
z_online = []
x_online = []
for i in z:
	z_online.extend(list(range(i[0], i[1] + 1)))
for i in x:
	x_online.extend(list(range(i[0], i[1] + 1)))
z_online = set(z_online)
ans = 0
for i in range(l, r + 1):
	test = map(lambda x: x + i, x_online)
	for _ in test:
		if _ in z_online:
			ans += 1
			break
print(ans)


(p, q, l, r) = map(int, input().split())
t = [0] * 1002
z = [list(map(int, input().split())) for i in range(p)]
x = [list(map(int, input().split())) for i in range(q)]
for (xl, xr) in x:
	for (zl, zr) in z:
		(a, b) = (zl - xr, zr - xl + 1)
		if b <= l:
			continue
		if a > r:
			break
		if a < l:
			a = l - 1
		if b <= r:
			t[b] -= 1
		t[a] += 1
for i in range(l, r + 1):
	t[i] += t[i - 1]
print(r - l + 1 - t[l:r + 1].count(0))


arr = list(map(int, input().split(' ')))
p = arr[0]
q = arr[1]
l = arr[2]
r = arr[3]
zarr = []
for i in range(p):
	m = list(map(int, input().split(' ')))
	zarr.append(m)
xarr = []
for i in range(q):
	m = list(map(int, input().split(' ')))
	xarr.append(m)
count = 0
times = []
for x in xarr:
	for z in zarr:
		if z[1] > x[0] + l:
			st = z[0] - x[1]
			end = z[1] - x[0]
			for i in range(l, r + 1):
				if st <= i and i <= end and (not i in times):
					times.append(i)
print(len(times))


(p, q, l, r) = map(int, input().split())
a1 = []
a2 = []
for i in range(p):
	a1.append(list(map(int, input().split())))
for i in range(q):
	a2.append(list(map(int, input().split())))
l1 = a1[-1][1] + 1
ans = 0
avail1 = [0] * l1
for i in range(p):
	for j in range(a1[i][0], a1[i][1] + 1):
		avail1[j] = 1
for t in range(l, r + 1):
	flag = False
	for i in range(q):
		for j in range(a2[i][0] + t, min(a2[i][1] + 1 + t, l1)):
			if avail1[j]:
				ans += 1
				flag = True
				break
		if flag:
			break
print(ans)


p = input().split(' ')
q = int(p[1])
l = int(p[2])
r = int(p[3])
p = int(p[0])
first1 = list()
first2 = list()
last1 = list()
last2 = list()
total = 0
for i in range(0, p):
	a = input().split(' ')
	first1.append(int(a[0]))
	last1.append(int(a[1]))
for i in range(0, q):
	a = input().split(' ')
	first2.append(int(a[0]))
	last2.append(int(a[1]))
for i in range(l, r + 1):
	flag = 0
	for k in range(0, len(first1)):
		for j in range(0, len(first2)):
			if first2[j] + i <= last1[k] and last2[j] + i >= first1[k]:
				total += 1
				flag = 1
				break
		if flag == 1:
			break
print(total)


(p, q, l, r) = map(int, input().split())
Z = []
X = []
for i in range(p):
	a = list(map(int, input().split()))
	Z.append(a)
for i in range(q):
	b = list(map(int, input().split()))
	X.append(b)
total = 0
for i in range(l, r + 1):
	f = 0
	for j in range(q):
		(c, d) = (X[j][0] + i, X[j][1] + i)
		for k in range(p):
			if Z[k][1] < c or Z[k][0] > d:
				pass
			else:
				f = 1
				break
		if f == 1:
			break
	if f == 0:
		total += 1
print(r - l + 1 - total)


def calc_overlap(a, b, l, r):
	if a[1] < b[0] + l:
		return None
	min_offset = max(a[0] - b[1] - l, 0)
	max_offset = a[1] - b[0] - l
	return (min_offset, min(max_offset, r - l))

def process_overlaps(overlaps):
	overlaps = sorted(overlaps)

def main():
	(p, q, l, r) = map(int, input().split())
	little_x = []
	little_z = []
	for __ in range(p):
		(a, b) = map(int, input().split())
		little_z.append((a, b))
	for __ in range(q):
		(a, b) = map(int, input().split())
		little_x.append((a, b))
	overlaps = []
	for hour_z in little_z:
		for hour_x in little_x:
			overlap = calc_overlap(hour_z, hour_x, l, r)
			if overlap is not None:
				overlaps.append(overlap)
	max_hour = -1
	result = 0
	for overlap in sorted(overlaps):
		diff = overlap[1] - max(overlap[0] - 1, max_hour)
		result += diff if diff > 0 else 0
		max_hour = max(overlap[1], max_hour)
	print(result)
main()


(p, q, l, r) = map(int, input().split())
(x, z) = ([False] * 1001, [False] * 1001)
for i in range(p):
	(a, b) = map(int, input().split())
	for i in range(a, b + 1):
		z[i] = True
for i in range(q):
	(c, d) = map(int, input().split())
	for i in range(c, d + 1):
		x[i] = True

def fn(t, x, z):
	for i in range(len(x) - t):
		if z[i + t] and x[i]:
			return 1
	return 0
ans = 0
for t in range(l, r + 1):
	ans += fn(t, x, z)
print(ans)


def mi():
	return map(int, input().split())
(n, m, l, r) = mi()
(a, b) = ([0] * n, [0] * n)
(c, d) = ([0] * m, [0] * m)
ea = [0] * 0
for i in range(n):
	(a[i], b[i]) = mi()
	ea[a[i]:b[i] + 1] = [1] * (b[i] + 1 - a[i])
for i in range(m):
	(c[i], d[i]) = mi()
count = 0
for t in range(l, r + 1):
	flag = 0
	for i in range(m):
		nl = c[i] + t
		nr = d[i] + t
		for ii in range(n):
			if a[ii] >= nl and a[ii] <= nr or (b[ii] >= nl and b[ii] <= nr) or (a[ii] >= nl and b[ii] <= nr) or (a[ii] <= nl and b[ii] >= nr):
				flag = 1
				break
	if flag:
		count += 1
print(count)


(p, q, l, r) = map(int, input().split())
x = []
z = []
for i in range(p):
	(a, b) = map(int, input().split())
	for i in range(a, b + 1):
		z.append(i)
for i in range(q):
	(a, b) = map(int, input().split())
	for i in range(a, b + 1):
		x.append(i)
t = 0
for i in range(l, r + 1):
	for val in x:
		if val + i in z:
			t += 1
			break
print(t)


import os
import sys
from math import *
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def value():
	return map(int, input().split())

def array():
	return [int(i) for i in input().split()]
(p, q, l, r) = value()
pre = [0] * 1001
for i in range(p):
	(a, b) = value()
	for j in range(a, b + 1):
		pre[j] = 1
B = []
for i in range(q):
	(a, b) = value()
	B.append((a, b))
ans = 0
for t in range(l, r + 1):
	for b in B:
		f = 0
		for i in range(b[0] + t, b[1] + t + 1):
			if i < 1001 and pre[i] == 1:
				f = 1
				break
		if f == 1:
			ans += 1
			break
print(ans)


(p, q, l, r) = map(int, input().split())
tz = []
tx = []
n = 0
for i in range(p):
	tz.append(list(map(int, input().split())))
for j in range(q):
	tx.append(list(map(int, input().split())))
ztimes = []
xtimes = []
for z in tz:
	for c in range(z[0], z[1] + 1):
		ztimes.append(c)
for x in tx:
	for d in range(x[0], x[1] + 1):
		xtimes.append(d + l)
for t in range(l, r + 1):
	for y in ztimes:
		if y in xtimes:
			n += 1
			break
	xtimes = [e + 1 for e in xtimes]
print(n)


from sys import stdin, stdout
from collections import deque, Counter, defaultdict
from math import factorial as fact

def ii():
	return int(stdin.readline())

def mi():
	return map(int, stdin.readline().split())

def li():
	return list(mi())

def si():
	return stdin.readline()
(n, q, l, r) = mi()
l1 = []
l2 = []
for _ in range(n):
	(a, b) = mi()
	l1 += [x for x in range(a, b + 1)]
for _ in range(q):
	(a, b) = mi()
	l2 += [x for x in range(a, b + 1)]
t = l
ans = 0
while r >= t:
	for x in l2:
		if x + t in l1:
			ans += 1
			break
	t += 1
print(ans)


(P, Q, L, R) = [int(num) for num in input().split()]
aa = []
for p in range(P):
	aa.append([int(num) for num in input().split()])
cc = []
for q in range(Q):
	cc.append([int(num) for num in input().split()])

def getLRRange(a, c, l, r):
	of = a[0] - c[1]
	ol = a[1] - c[0]
	total = ol - of
	if ol < 0:
		return None
	of = max(l, of)
	ol = min(ol, r)
	if ol < of:
		return None
	return [of, ol]

def vec_add(lst, add):
	for i in range(len(lst)):
		lst[i] += add
	return lst

def union(a):
	b = []
	for (begin, end) in sorted(a):
		if b and b[-1][1] >= begin - 1:
			b[-1][1] = max(b[-1][1], end)
		else:
			b.append([begin, end])
	return b

def countRangeTotal(ranges):
	sum = 0
	for (l, r) in ranges:
		sum += r - l + 1
	return sum
ranges = []
for a in aa:
	for c in cc:
		range_ = getLRRange(a, c, L, R)
		if range_ is not None:
			ranges.append(range_)
print(countRangeTotal(union(ranges)))


(p, q, l, r) = list(map(int, input().split()))
a = [0] * p
b = [0] * p
for i in range(p):
	(a[i], b[i]) = list(map(int, input().split()))
c = [0] * q
d = [0] * q
for i in range(q):
	(c[i], d[i]) = list(map(int, input().split()))
maxtime = max(max(b), max(d)) + 1
x = ['0'] * maxtime
z = ['0'] * maxtime
for i in range(p):
	for j in range(a[i], b[i] + 1):
		x[j] = '1'
for i in range(q):
	for j in range(c[i], d[i] + 1):
		z[j] = '1'
xs = ''
for i in x:
	xs += i
zs = ''
for i in z:
	zs += i
x = int(xs, 2)
z = int(zs, 2)
z = z >> l
count = 0
for i in range(l, r + 1):
	if x & z != 0:
		count += 1
	z = z >> 1
print(count)