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.