레이팅 미적용농부 존은 편의상 \(1 \ldots N\)으로 번호가 매겨진 \(N\)마리의 소들을 데리고 매년 열리는 소 장기자랑에 참가하기 위해 카운티 축제에 간다! \(i\)번째 소는 무게 \(w_i\)와 재능 수준 \(t_i\)를 가지며, 둘 다 정수이다.
도착하자마자 농부 존은 올해 장기자랑의 새로운 규칙에 꽤 놀란다.
(i) 총 무게가 \(W\) 이상인 소들의 그룹이 참가해야 하며(강한 개체가 아니라 강한 소 팀들이 경쟁하도록 보장하기 위해서이다),
(ii) 총 재능 대 총 무게의 비율이 가장 큰 그룹이 우승한다.
농부 존은 자신의 소들을 모두 합치면 무게가 \(W\) 이상이므로 조건 (i)을 만족하는 팀을 참가시킬 수 있음을 안다. 그러한 팀에 대해 그가 달성할 수 있는 재능 대 무게의 최적 비율을 구하도록 도와주자.
출제자: Brian Dean
출제자: Brian Dean
입력의 첫째 줄에 \(N\) (\(1 \leq N \leq 250\))과 \(W\) (\(1 \leq W \leq 1000\))가 주어진다. 다음 \(N\)개의 줄에는 각각 소 한 마리가 두 정수 \(w_i\) (\(1 \leq w_i \leq 10^6\))와 \(t_i\) (\(1 \leq t_i \leq 10^3\))로 주어진다.
총 무게가 \(W\) 이상인 소들의 그룹으로 농부 존이 달성할 수 있는 총 재능 대 총 무게 비율의 최댓값을 구한다. 답이 \(A\)라면, 출력을 정수로 유지하기 위해 \(1000A\)의 내림값을 출력한다(내림 연산은 해당 수가 이미 정수가 아닌 경우 소수 부분을 버리고 정수로 내림하는 것이다).
talent.in · 출력을 쓸 파일 talent.out3 15
20 21
10 11
30 311066In this example, the best talent-to-weight ratio overall would be to use just
the single cow with talent 11 and weight 10, but since we need at least 15
units of weight, the optimal solution ends up being to use this cow plus the cow
with talent 21 and weight 20. This gives a talent-to-weight ratio of
(11+21)/(10+20) = 32/30 = 1.0666666..., which when multiplied by 1000 and
floored gives 1066.