Moo University Team Tryouts

Interview

Time limit1sMemory limit1024 MB

Summary

Given N calves with heights and weights, find the largest team where every calf satisfies A(H-h)+B(W-w)<=C, with h and w the team's minimum height and weight.

Level: Medium4 of 10
Topics: Brute force, Sorting, Implementation
Solved: No attempts yet

Problem

N (1 ≤ N ≤ 1,000) calves try out for the Moo U gymnastics team this year, each with a positive integer height and a weight less than 100,000. The goal is to select as many calves as possible for the team. The team must satisfy one constraint: the height H and weight W of each calf on the team must obey the following inequality.

$A(H-h) + B(W-w) \le C$

Here h and w are the minimum height and weight over all calves on the team. A, B, and C are positive integer constants less than 10,000. Compute the maximum number of calves on the team.

Input

Line 1 contains the integer N. Line 2 contains three space-separated integers A, B, and C. Lines 3 through N+2 each contain the height and weight of one calf, separated by a space.

Output

Line 1 contains one integer, the maximum number of calves on the team.

Hint

Calves 1, 2, 3, 4 and 7, for example, form a legal team. A larger team is impossible.

Examples1

Example 1

Input

Expected output