Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Tienes que contratar trabajadores para un proyecto de construcción. Existen N candidatos solicitando este trabajo, enumerados desde el 1 hasta el N inclusive. Cada candidato k exige que si es contratado le paguen por lo menos S _k dólares. También cada candidato k tiene un nivel de calificación Q _k . Las regulaciones en la industria de la construcción requieren que les pagues a los trabajadores en proporción con su nivel de calificación en relación con respecto a otro trabajador. Por ejemplo, si contratas a dos trabajadores A y B, su proporción en el nivel de calificación es Q _A = 3 * Q _B , entonces debes pagarle al trabajador A exactamente  tres veces lo que le pagas al trabajador B . Puedes pagar a los trabajadores cantidades de dinero no enteras. Esto incluye cantidades que no pueden escribirse con un número finito de dígitos decimales, como un tercio (1/3) o un sexto (1/6) de un dólar.

Usted tienes W dólares disponibles para contratar la mayor cantidad de trabajadores posibles. Tú decides a quien contratas y cuanto le pagas a ellos, pero debes tener en cuenta el salario mínimo posible de estos trabajadores contratados y que cumplan con la regulación de la Industria de la Construcción. Debes tratar de ajustar tus gastos a tus W dólares disponibles.

La naturaleza de tu proyecto es tal que el nivel de calificación es completamente irrelevante, sólo estas interesado en aumentar al máximo  número de obreros sin considerar su nivel de calificación.  Sin embargo, si hay más de una manera de lograr esto, entonces debes seleccionar el modo dónde la cantidad total de dinero que tienes que pagar a tus obreros sea las más pequeña posible. En caso de que exista más de una manera de lograr esto, entonces serás indiferente entre estas maneras y estarás satisfecho con cualquiera de ellas.

TAREA

Escribe un programa que, dados los diferentes salarios requeridos y el nivel de calificación de los candidatos, así como la cantidad de dinero que tienes, determine a qué candidatos debes contratar. Debe contratar tantos de ellos como sea posible y debes hacerlo con la menor cantidad de dinero posible, mientras cumplas con las regulaciones de la industria especificadas anteriormente.

RESTRICCIONES
1 <= N <= 500,000              El número de candidatos
1 <= S _k <= 20,000               El mínimo salario requerido por el candidato k
1 <= Q _k <= 20,000               El nivel de calificación del candidato k
1 <= W <= 10,000,000,000  La cantidad de dinero que tienes disponible

NOTA IMPORTANTE

El valor máximo de W no  es  representable en 32 bits. Debes usar un tipo de dato de 64 bits, como long long en C/C++ o int64 en Pascal, para guardar el valor de W en una sola variable.

Input

Tu programa debe leer desde la entrada estándar los siguientes datos:

• La primera línea contiene dos enteros N y W , separados por un espacio.
• Las siguientes N líneas describen los candidatos, un candidato por línea. La k-ésima de estas líneas describe al candidato identificado con el numero k y contiene los enteros S _k y Q _k , separados por un espacio.

Output

Tu programa debe escribir a la salida estándar los siguientes datos:

• La primera línea debe contener un sólo entero H , El número de trabajadores que contratarás.
• Las siguientes H líneas deben listar los números de identificación de los candidatos seleccionados para ser contratados (cada uno de estos números diferentes entre 1 y N ), uno por línea, en cualquier orden.

Sample test(s)

Hints

Hint

Ejemplo 1 : La única combinación para que puedas permitirte el lujo de contratar a dos trabajadores y todavía cumplir todas las restricciones es si seleccionas a los trabajadores 2 y 3. Puedes pagarles 80 y 8 dólares respectivamente y ajustados en tu presupuesto de 100 dólares.

Ejemplo 2 : Aquí puedes permitirte el lujo de contratar a todos los  trabajadores. Pagándole 1 dólar al trabajador 1 y 1,50 dólares a los trabajadores 2 y 3, y has logrado contratar a todos los trabajadores con los 4 dólares que tenías disponible.

Ejemplo 3 : Aquí no puedes permitirte el lujo de contratar a todos los  trabajadores, esto te costaría  60 dólares, pero puedes permitirte el lujo de contratar a cualquiera dos de ellos. Seleccionas contratar a los trabajadores 2 y 3 porque ellos te costarían la suma más pequeña de dinero, comparada a las otras combinaciones de contratación de dos-trabajadores. Puedes pagar 10 dólares al obrero 2 y 15 dólares al obrero 3 para un total de 25 dólares. Si contrataras a los obreros 1 y 2  tendrías que pagarles por lo menos 10 y 20 dólares respectivamente. Si contrataras al 1 y al 3, entonces tendrías que pagarles por lo menos 10 y 30 dólares respectivamente.