Talent Show.
El granjero John lleva sus vacas, convenientemente numeradas , a la feria del condado, para competir en el concurso anual de talentos bovinos. Su -ésima vaca tiene un peso y un nivel de talento , ambos enteros.
A su llegada, el granjero John se sorprende de las nuevas reglas del concurso de talentos de este año:
(i) Un grupo de vacas con un peso total de al menos (para asegurarse de que compiten equipos fuertes de vacas, y no sólo individuos fuertes), y
(ii) El grupo con la mayor relación entre el talento total y el peso total ganará.
FJ observa que todas sus vacas juntas tienen un peso mínimo de por lo que debería poder inscribir un equipo que satisfaga (i). Ayúdele a determinar la relación óptima entre el talento y el peso que puede lograr para cualquier equipo de este tipo.
Entrada
La primera línea de entrada contiene y . Las siguientes líneas describen cada una una vaca utilizando dos enteros y .
Salida
Determine la mayor relación posible entre el talento total y el peso total que el granjero John puede alcanzar utilizando un grupo de vacas de peso total al menos . Si su respuesta es , por favor imprima el piso de para que la salida tenga un valor entero (la operación del piso descarta cualquier parte fraccionaria redondeando hacia abajo a un número entero, si el número en cuestión no es ya un número entero).
Ejemplo de Entrada
3 15
20 21
10 11
30 31
Ejemplo de Salida
1066
En este ejemplo, la mejor relación talento-peso en general sería utilizar sólo la vaca con talento 11 y peso 10, pero como necesitamos al menos 15 unidades de peso, la solución óptima acaba siendo utilizar esta vaca más la vaca con talento 21 y peso 20. Esto da una relación talento-peso de , que multiplicado por 1.000 y con un factor de flotación da 1066.
Comments