题目描述

给定 $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$。

现在，你要用最少的花费，使得所有二元组都不可以被操作.

输入格式

第一行有三个正整数 $n,p,q$。

接下来 $n$ 行每行有两个正整数 $a_i,b_i$ 表示第 $i$ 个二元组 $(a_i,b_i)$。

输出格式

输出一行一个整数，表示你所求得的最小花费。

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

提示

样例解释

对于第一个样例，我们可以先后进行 $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$。