1074 : 선수 선발
- 제한시간
- 1000 ms
- 메모리제한
- 128 MB
- 해결횟수
- 0 회
- 시도횟수
- 1 회
문제
농부 창호는 축산업자들이 여는 운동회를 위해 자신이 기르는 소들 중에서 몇 마리를 골라서 팀을 구성하고자 한다.
창호는 최대 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 |