Minimum Cost to Invalidate Tuples

You are given (n) ordered pairs ((a_i, b_i)). A pair is considered operable if and only if (b_i > 0). You may perform the following two operations any number of times in any order, where each operation is applied simultaneously to every operable pair:

1. Operation 1: For every operable pair, update (b_i \gets b_i - a_i). This operation costs (p).

2. Operation 2: For every operable pair, swap the two values. In other words, perform (\operatorname{Swap}(a_i, b_i)) where (\operatorname{Swap}(x,y)= (y,x)). This operation costs (q).

Your goal is to choose a sequence of these operations (applied globally) with the minimum total cost so that at the end every pair becomes non-operable (i.e. (b_i \le 0) for all (i)).

A key observation is that for any single pair ((a, b)) with (b>0), one straightforward strategy is to repeatedly apply Operation 1. After (r) applications, the value of (b) will be (b - r \cdot a), and you need (r \ge \lceil \frac{b}{a} \rceil) to have (b \le 0). Another strategy is to perform one swap operation immediately; the pair then becomes ((b, a)) and subsequently applying Operation 1 will reduce the new second element (a). In that case, you need (r \ge \lceil \frac{a}{b} \rceil) Operation 1’s after a swap.

Since the operations are applied globally to all pairs, you must choose one sequence that guarantees termination for every pair. Therefore, if we let

[ \text{cost}{\text{no-swap}} = p \times \max{{i:,b_i>0}} \Bigl\lceil \frac{b_i}{a_i} \Bigr\rceil, ]

and

[ \text{cost}{\text{swap}} = q + p \times \max{{i:,b_i>0}} \Bigl\lceil \frac{a_i}{b_i} \Bigr\rceil, ]

then the answer is simply

[ \min\Bigl{\text{cost}{\text{no-swap}},,\text{cost}{\text{swap}}\Bigr}. ]

Note that pairs for which (b_i \le 0) initially are ignored. This problem requires you to compute the minimum total cost based on the above observation.

inputFormat

The first line contains three integers (n), (p), and (q) ( (1 \le n \le 10^5)). Each of the following (n) lines contains two positive integers (a_i) and (b_i). A pair ((a_i, b_i)) is operable if and only if (b_i > 0).

outputFormat

Output one integer: the minimum total cost required so that for every pair, after performing a prefix of the sequence of operations, (b_i \le 0) holds.

sample

3 3 2
3 10
4 2
5 5

8