B. The Search for Balance
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Ying is a gaming fan and is developing a new RPG. In this game, each player starts with a character that has $$$0$$$ attack points and $$$0$$$ defense points. To customize their character, players can use power-ups.

The game will have $$$N$$$ power-ups, and each one can only be used once. Each power-up is defined by a pair of integers $$$(a, d)$$$, which modifies the attack and defense points. If a player with $$$A$$$ attack and $$$D$$$ defense chooses a power-up $$$(a, d)$$$, their character's new attributes will be $$$A+a$$$ attack and $$$D+d$$$ defense. Note that the values $$$a$$$ and $$$d$$$ can be negative, which means the final attack and defense attributes can also become negative.

The game developers say that a character is "balanced" if its final attack points, $$$A$$$, are in the interval $$$[A_1, A_2]$$$ and its final defense points, $$$D$$$, are in the interval $$$[D_1, D_2]$$$.

Ying wants to know in how many ways a player can obtain a balanced character. A "way" is defined by a distinct set of power-ups. Two sets are distinct if one contains a power-up that the other does not. The order in which the power-ups are applied does not matter.

Input

The first line contains an integer $$$N$$$ ($$$1 \leq N \leq 35$$$), the number of power-ups in the game. The next $$$N$$$ lines describe the power-ups. Each of these lines contains two integers $$$a$$$ and $$$d$$$ ($$$-10^9 \leq a, d \leq 10^9$$$). The last line contains four integers $$$A_1, D_1, A_2$$$ and $$$D_2$$$ ($$$-10^{12} \leq A_1 \leq A_2 \leq 10^{12}$$$ and $$$-10^{12} \leq D_1 \leq D_2 \leq 10^{12}$$$), which define the intervals for a character to be considered balanced.

Output

Print a single line containing an integer representing the number of distinct sets of power-ups that result in a balanced character.

Examples
Input
8
1 1
1 -1
-1 1
-1 -1
1 1
1 -1
-1 1
-1 -1
-1000 -1000 1000 1000
Output
256
Input
8
0 0
1 1
2 1
2 0
3 0
1 1
0 2
5 5
5 3 5 3
Output
2