Talent Show.


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem types
Allowed languages
C, C++, Java, Pascal, Python, VB

El granjero John lleva sus N vacas, convenientemente numeradas 1...N, a la feria del condado, para competir en el concurso anual de talentos bovinos. Su i-ésima vaca tiene un peso w_i y un nivel de talento t_i, 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 W (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 W 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 N(1 \leq N \leq 250) y W(1 \leq W \leq 10^3). Las siguientes N líneas describen cada una una vaca utilizando dos enteros w_i (1\leq wi \leq 10^6) y t_i (1 \leq ti \leq 10^3).

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 W. Si su respuesta es A, por favor imprima el piso de 1000A 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 (11+21)/(10+20) = 32/30 = 1,0666666..., que multiplicado por 1.000 y con un factor de flotación da 1066.


Comments

There are no comments at the moment.