Problem Description

Given \( n \) pairs \((a_i, b_i)\), a pair is no longer operable when \( b_i \leq 0 \). You can perform two operations:

1. For all operable pairs, execute \( b_i \gets b_i - a_i \), which reduces \( b_i \) by \( a_i \), costing \( p \).

2. For all operable pairs, execute \( \text{Swap}(a_i, b_i) \), where \( \text{Swap}(x, y) \) denotes swapping the values of \( x \) and \( y \), costing \( q \).

You need to use the minimum 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 a single integer, the minimum cost required.

Sample Input and Output

Sample Input #1

4 9 5
1 7
1 4
6 5
4 2

Sample Output #1

23

Sample Input #2

3 500 3
4 6
3 5
8 1

Sample Output #2

1000

Sample Input #3

2 1 1000
1 500
2 800

Sample Output #3

500

Notes

Sample Explanation

For the first sample, we can perform 1 operation 1, 1 operation 2, and 1 operation 1, with a minimum cost of \( 9 + 5 + 9 = 23 \).
For the second sample, we can perform 2 operations 1, with a minimum cost of \( 500 \times 2 = 1000 \).
For the third sample, we can perform 500 operations 1, with a minimum cost of \( 1 \times 500 = 500 \).

Data Range

This problem uses subtask testing.

• 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 additional constraints.

For \( 100\% \) of the data, \( 1 \le n \le 10^5 \), \( 1 \le p, q \le 10^7 \), \( 1 \le a_i, b_i \le 10^5 \).

见题面 Input 部分

见题面 Output 部分