Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Chat Online

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputLittle 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

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/15/2018 06:36:01 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|