USACO 2004, poj 2008- 선수 선발 > 문제은행 : 정보올림피아드&알고리즘



1074 : 선수 선발

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
7 회   
시도횟수
63 회   

문제

농부 창호는 축산업자들이 여는 운동회를 위해 자신이 기르는 소들 중에서 몇 마리를 골라서 팀을 구성하고자 한다.

 

창호는 최대 1,000마리의 소를 키우며, 팀에 들어갈 수 있는 소는 자신의 신장 H와 체중W에 대해서 다음을 만족해야 한다.

 

A*(H-h)+B*(W-w)<=C
A,B,C는 정수이고, h, w는 각각 멤버 소중에서 가장 작은 신장과 가장 작은 체중을 뜻한다.

 

소들이 많을수록 운동회에서 유리해지기 때문에 최대한 많은 소를 뽑을 수 있는 프로그램을 작성하라.


입력형식

입력의 첫 번째 줄에는 소의 수(N≤1,000), 두 번째 줄에는 정수 A,B,C의 값(1≤A,B,C≤10,000), 세 번째 줄부터 연속된 N개의 양의 정수로 이루어진 소의 신장 H, 소의 체중 W가 공백을 사이에 두고 입력된다(1≤H,W≤100,000).

출력형식

위의 조것을 만족하여 팀을 선발했을 때, 뽑히는 소들의 최대 마리수를 출력한다.

입력 예

8
1 2 4
5 1
3 2
2 3
2 1
7 2
6 4
5 1
4 3

출력 예

5


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010-2019 jungol. All right reserved.

TOP