Problem
La figlia del re di Flatlandia sta per sposare il principe azzurro.
Il principe vuole regalare alla principessa dei tesori, ma non è sicuro di quali diamanti scegliere dalla sua collezione.
Ci sono n diamanti nella collezione del principe, ciascuno caratterizzato da peso w
i e valore v
i.
Il principe vuole dare i diamanti più costosi, ma il re è furbo e non accetterà diamanti con un peso totale superiore a R. D'altra parte, il principe si considererà avido per il resto della sua vita se regala diamanti con un peso complessivo inferiore a L.
Aiuta il principe a scegliere un set di diamanti con il valore totale più alto in modo che il peso totale sia nel segmento [L, R].
Inserimento:
La prima riga contiene il numero n (1 <= n <= 32), L e R (0 <= L <= R <= 10
18).
Le n righe successive descrivono i diamanti e contengono due numeri ciascuna: il peso e il valore del diamante corrispondente (1 <= wi, vi <= 10
15).
Uscita:
La prima riga dell'output dovrebbe contenere k - il numero di diamanti da dare alla principessa.
La seconda riga dovrebbe contenere i numeri dei diamanti da dare.
I diamanti sono numerati da 1 a n nell'ordine in cui appaiono nell'input.
Se è impossibile comporre un regalo per la principessa, stampa 0 nella prima riga dell'output.
Esempi:
| Input |
Uscita |
3 6 8
3 10
7 3
8 2 |
1
2 |