#P1493. Uniform Pear Distribution

    ID: 14779 Type: Default 1000ms 256MiB

Uniform Pear Distribution

Uniform Pear Distribution

Finley has harvested many pears from his garden. Each pear is characterized by two attributes: \(A_i\) (its size) and \(B_i\) (its sweetness). Finley wants to distribute pears to the children, but to avoid any child getting a notably smaller pear, he wishes to pick a set of pears that are almost uniform.

In any chosen set \(S\) of pears, let \(A_0 = \min_{i \in S} A_i\) and \(B_0 = \min_{i \in S} B_i\). The set \(S\) is acceptable if for every pear \(i \in S\), the following inequality holds:

\(C_1 \times (A_i - A_0) + C_2 \times (B_i - B_0) \le C_3\),

where \(C_1\), \(C_2\), and \(C_3\) are given constants. Your task is to determine the maximum number of pears that can be selected such that they satisfy the above condition.

inputFormat

The first line contains four integers \(n\), \(C_1\), \(C_2\), and \(C_3\), where \(n\) is the number of pears.

Each of the following \(n\) lines contains two integers \(A_i\) and \(B_i\) representing the size and sweetness of the \(i\)-th pear.

outputFormat

Output a single integer: the maximum number of pears that can be selected such that in the selected set with minimum values \(A_0\) and \(B_0\), every pear \(i\) satisfies \(C_1 \times (A_i - A_0) + C_2 \times (B_i - B_0) \le C_3\).

sample

5 1 1 10
1 2
3 4
2 2
10 10
4 3
4

</p>