문제
농부 창호는 축산업자들이 여는 운동회를 위해 자신이 기르는 소들 중에서 몇 마리를 골라서 팀을 구성하고자 한다.
창호는 최대 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
출처
USACO 2004, poj 2008
로그인해야 코드를 작성할 수 있어요.