Problem
A filha do Rei de Flatland está prestes a se casar com o Príncipe Encantado.
O príncipe quer dar tesouros à princesa, mas não tem certeza de quais diamantes escolher em sua coleção.
Existem n diamantes na coleção do príncipe, cada um caracterizado pelo peso w
i e valor v
i.
O príncipe quer dar os diamantes mais caros, mas o rei é esperto e não aceitará diamantes com peso total superior a R. Por outro lado, o príncipe se considerará ganancioso pelo resto da vida se der diamantes com um peso total inferior a L.
Ajude o príncipe a escolher um conjunto de diamantes com o maior valor total para que o peso total fique no segmento [L, R].
Entrada:
A primeira linha contém o número n (1 <= n <= 32), L e R (0 <= L <= R <= 10
18).
As próximas n linhas descrevem os diamantes e contêm dois números cada - o peso e o valor do diamante correspondente (1 <= wi, vi <= 10
15).
Saída:
A primeira linha da saída deve conter k - o número de diamantes a serem dados à princesa.
A segunda linha deve conter os números dos ouros a serem dados.
Os diamantes são numerados de 1 a n na ordem em que aparecem na entrada.
Se for impossível compor um presente para a princesa, imprima 0 na primeira linha da saída.
Exemplos:
| Entrada |
Saída |
3 6 8
3 10
7 3
8 2 |
1
2 |