To celebrate the National Day of Country H, the King has invited $n$ ministers to play a prize game. First, he asks each minister to write an integer on their left hand and another on their right hand. The King also writes an integer on each of his own hands. Then, he asks the $n$ ministers to stand in a line, with the King standing at the very front of the queue. After the line is formed, all ministers receive a certain number of gold coins from the King. The number of gold coins received by each minister is calculated as: the product of the numbers on the left hands of everyone standing in front of that minister, divided by the number on their own right hand, rounded down to the nearest integer.

The King does not want any single minister to receive an excessive amount of rewards, so he asks you to help him rearrange the order of the queue such that the maximum reward received by any minister is minimized. Note that the King's position is always at the very front of the queue.

Input

The first line contains an integer $n$, representing the number of ministers.

The second line contains two integers $a$ and $b$, separated by a space, representing the integers on the King's left and right hands, respectively.

The next $n$ lines each contain two integers $a$ and $b$, separated by a space, representing the integers on each minister's left and right hands, respectively.

Output

Output a single line containing an integer, representing the minimum possible value of the maximum reward received by any minister after rearranging the queue.

Examples

Input 1

3
1 1
2 3
7 4
4 6

Output 1

2

Note

• If the ministers are arranged in the order 1, 2, 3, the maximum reward is 2.
• If the ministers are arranged in the order 1, 3, 2, the maximum reward is 2.
• If the ministers are arranged in the order 2, 1, 3, the maximum reward is 2.
• If the ministers are arranged in the order 2, 3, 1, the maximum reward is 9.
• If the ministers are arranged in the order 3, 1, 2, the maximum reward is 2.
• If the ministers are arranged in the order 3, 2, 1, the maximum reward is 9.

Therefore, the minimum possible value for the maximum reward is 2, so the output is 2.

Subtasks

For 20% of the data, $1\le n\le 10$ and $0< a,b< 8$.

For 40% of the data, $1\le n\le 20$ and $0< a,b< 8$.

For 60% of the data, $1\le n\le 100$.

For 60% of the data, the answer is guaranteed not to exceed $10^9$.

For 100% of the data, $1\le n\le 1{,}000$ and $0< a,b< 100\,00$.