Demi-finale 2009, épreuve machine - Cuisine fine

DIFFICULTE

LIMITE DE MEMOIRE

8192 ko

LIMITE DE TEMPS

2000 ms

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).

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.

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

Du type :

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).

EXEMPLE(S) D'ENTREE/SORTIE

Exemple 1
en entrée ...

4
250
30 5
20 7
300 8
300 10

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).