Problem
La fille du roi de Flatland est sur le point d'épouser le prince charmant.
Le prince veut offrir des trésors à la princesse, mais il ne sait pas quels diamants choisir dans sa collection.
Il y a n diamants dans la collection du prince, chacun caractérisé par un poids w
i et une valeur v
i.
Le prince veut donner les diamants les plus chers, mais le roi est intelligent et n'acceptera pas les diamants d'un poids total supérieur à R. En revanche, le prince se considérera gourmand pour le reste de sa vie s'il donne des diamants avec un poids total inférieur à L.
Aidez le prince à choisir un ensemble de diamants avec la valeur totale la plus élevée afin que le poids total soit dans le segment [L, R].
Saisie :
La première ligne contient le nombre n (1 <= n <= 32), L et R (0 <= L <= R <= 10
18).
Les n lignes suivantes décrivent les diamants et contiennent chacune deux nombres : le poids et la valeur du diamant correspondant (1 <= wi, vi <= 10
15).
Sortie :
La première ligne de la sortie doit contenir k - le nombre de diamants à donner à la princesse.
La deuxième ligne doit contenir les numéros des diamants à donner.
Les diamants sont numérotés de 1 à n dans l'ordre dans lequel ils apparaissent dans l'entrée.
S'il est impossible de composer un cadeau pour la princesse, écrivez 0 sur la première ligne de la sortie.
Exemples :
| Entrée |
Sortie |
3 6 8
3 10
7 3
8 2
| 1
2 |