Problem
La hija del Rey de Planilandia está a punto de casarse con el Príncipe Encantador.
El príncipe quiere darle tesoros a la princesa, pero no está seguro de qué diamantes elegir de su colección.
Hay n diamantes en la colección del príncipe, cada uno caracterizado por el peso w
i y el valor v
i.
El príncipe quiere dar los diamantes más caros, pero el rey es inteligente y no aceptará diamantes con un peso total superior a R. Por otro lado, el príncipe se considerará codicioso por el resto de su vida si da diamantes. con un peso total inferior a L.
Ayuda al príncipe a elegir un juego de diamantes con el valor total más alto para que el peso total esté en el segmento [L, R].
Entrada:
La primera línea contiene el número n (1 <= n <= 32), L y R (0 <= L <= R <= 10
18).
Las siguientes n líneas describen los diamantes y contienen dos números cada una: el peso y el valor del diamante correspondiente (1 <= wi, vi <= 10
15).
Salida:
La primera línea del resultado debe contener k: el número de diamantes que se le dará a la princesa.
La segunda línea debe contener los números de los diamantes que se van a dar.
Los diamantes se numeran del 1 al n en el orden en que aparecen en la entrada.
Si es imposible componer un regalo para la princesa, imprima 0 en la primera línea de la salida.
Ejemplos:
| Entrada |
Salida |
3 6 8
3 10
7 3
8 2 |
1
2 |