P6515 [QkOI#R1] Quark and Game

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.

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 one integer in one line, representing the minimum total cost.

### 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