P6515 [QkOI#R1] Quark and Game

给定 $n$ 个二元组 $(a_i,b_i)$，当 $b_i\le 0$ 时该二元组不再可以被操作。你可以执行两个操作： 1. 对于**所有**可以被操作的二元组，执行 $b_i\gets b_i-a_i$，即令 $b_i$ 的值减少 $a_i$，花费 $p$。 2. 对于**所有**可以被操作的二元组，执行 $\operatorname{Swap}(a_i,b_i)$，其中 $\operatorname{Swap}(x,y)$ 表示交换 $x,y$ 的值，花费 $q$。 现在，你要用最少的花费，使得所有二元组都不可以被操作.

无

无

### 样例解释 对于第一个样例，我们可以先后进行 $1$ 次操作 1，$1$ 次操作 2，$1$ 次操作 1，最小花费为 $9 + 5 + 9 = 23$。 对于第二个样例，我们可以进行 $2$ 次操作 1，最小花费为 $500 \times 2 = 1000$。 对于第三个样例，我们可以进行 $500$ 次操作 1，最小花费为 $1 \times 500 = 500$。 --- ### 数据范围 **本题采用捆绑测试。** - 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）：无特殊限制。 对于 $100\%$ 的数据，$1\le n\le 10^5$，$1\le p,q\le 10^7$，$1\le a_i,b_i\le 10^5$。