Maximized Subset Product

You are given n elements, numbered from 1 to n. Each element j has two positive integer weights, a_j and b_j.

You need to choose a subset S of the set \([1, n]\) such that the following expression is maximized:

$$\Big(\sum_{j=1}^{n} a_j\,[j\in S]\Big)\cdot\Big(\sum_{j=1}^{n} b_j\,[j\notin S]\Big), $$

Here the indicator function \([P]\) equals 1 if the predicate P is true, and 0 otherwise.

This problem is NP-hard in general. However, it is guaranteed that every weight \(a_j\) and \(b_j\) is independently and uniformly randomly generated in \([1,A]\) and \([1,B]\) respectively. Due to this restriction, the maximum answer is uniquely determined by the given input.

Given n, A, B and all the weights \((a_j,b_j)\), output the maximum possible value of the above expression.

inputFormat

The first line contains three integers n, A and B.

Each of the next n lines contains two integers aj and bj representing the weights of the j-th element.

All numbers are separated by spaces.

outputFormat

Output a single integer representing the maximum value of \( \Big(\sum_{j=1}^{n} a_j\,[j\in S]\Big)\cdot\Big(\sum_{j=1}^{n} b_j\,[j\notin S]\Big). \)

sample

3 10 10
1 1
2 2
3 3

9