Module: Le problème du sac à dos


Problem

4 /6


Tirelire

Problem

Le poids E d'une tirelire vide et le poids F d'une tirelire avec des pièces sont réglés. La tirelire peut contenir des pièces de types N, pour chaque type la valeur Pi et le poids Wi< /sub> sont connus une pièce. Trouvez le montant minimum et maximum d'argent qui peut être dans la tirelire.

Entrée : 
- la première ligne contient les nombres E et F (\(1<=E<=F<=10000\)< /span>);
- dans le second - nombre N (\(1<=N<=500\));
- dans les lignes N suivantes - deux chiffres chacune, Pi et Wi < / code>(\(1<=Pi<=50000\), \(1<=Wi<=10000\ ) ).
Tous les nombres sont des entiers.

Sortie : deux nombres séparés par un espace sont affichés - les sommes minimale et maximale. Si la tirelire ne peut pas avoir exactement le poids spécifié, à condition qu'elle soit remplie de pièces des types spécifiés, écrivez "Ceci est impossible.".
 
 

 

Exemples
1000 1100
2
1 1
5 2
1000 1010
2
6 3
2 2
1000 2000
1
10 3
# Entrée Sortie
1 100 250
2 10 16
3 C'est impossible.

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!