Cuisine fine – Épreuve régionale 2009

Joseph Marchand a un placard bourré de vieux paquets de pâtes entamés.

On vous donne la quantité de pâtes restantes dans chaque paquet p~i~, son temps de cuisson t~i~, et la quantité Q de pâtes que Joseph Marchand souhaite manger ce soir. Il voudrait prélever cette quantité Q dans les divers paquets en en vidant le plus possible pour faire de la place dans son placard. S'il a le choix entre deux paquets où il reste la même quantité de pâtes, il préfère celles qui cuisent le plus vite, et s'il y a encore égalité, il préfère le premier qu'il trouve (c'est à dire le premier que l'on vous donne).

Dites-lui combien de paquets il va utiliser, combien de paquets il va pouvoir vider, et donnez lui l'ordre dans lequel il doit mettre ses paquets dans la casserole afin d'atteindre une cuisson uniforme (s'il doit mettre plusieurs paquets en même temps, il met le premier qu'il trouve, c'est à dire le premier dans l'ordre où l'on vous les donne).

ENTREE

N nombre de paquets, Q quantité qu'il souhaite manger, suivis de N lignes de 2 entiers : poids de pâtes contenu dans le paquet et temps de cuisson.

LIMITES

Q \<= 10\^9, somme des poids \<= 10\^9, N (nombre de paquets) \<= 100 000

SORTIE

Du type :

1
2
3
4

Joseph utilisera 3 paquet(s) et pourra en jeter 2.
Il doit commencer par mettre le paquet 2 a cuire.
Il mettra le paquet 1 au bout de 1 minute(s).
Il mettra le paquet 0 au bout de 3 minute(s).