Description

Given $n$ pairs $(a_i,b_i)$. When $b_i \le 0$, this pair can no longer be operated on. You can perform two operations:

1. For all operable pairs, do $b_i \gets b_i - a_i$, i.e., decrease $b_i$ by $a_i$, with cost $p$.

2. For all operable pairs, do $\operatorname{Swap}(a_i,b_i)$, where $\operatorname{Swap}(x,y)$ means swapping the values of $x$ and $y$, with cost $q$.

Now, you need to spend the minimum total cost to make all pairs non-operable.

Input Format

The first line contains three positive integers $n,p,q$.

The next $n$ lines each contain two positive integers $a_i,b_i$, representing the $i$-th pair $(a_i,b_i)$.

Output Format

Output one integer in one line, representing the minimum total cost.

4 9 5
1 7
1 4
6 5
4 2

23

3 500 3
4 6
3 5
8 1

1000

2 1 1000
1 500
2 800

500

Hint

Sample Explanation

For the first sample, we can perform operation 1 once, operation 2 once, and operation 1 once in this order. The minimum cost is $9 + 5 + 9 = 23$.
For the second sample, we can perform operation 1 twice. The minimum cost is $500 \times 2 = 1000$.
For the third sample, we can perform operation 1 $500$ times. The minimum cost is $1 \times 500 = 500$.

Constraints

This problem uses bundled testdata.

• Subtask 1 (10 pts): $n \le 100$, $a_i,b_i \le 20$.
• Subtask 2 (20 pts): $n \le 1000$, $a_i,b_i \le 1000$.
• Subtask 3 (17 pts): $p = 1$, $q = 10^7$.
• Subtask 4 (53 pts): no special constraints.

For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le p,q \le 10^7$, $1 \le a_i,b_i \le 10^5$.

Translated by ChatGPT 5