جعبه پول
Problem
وزن
E قلک خالی و وزن
F قلک با سکه تنظیم شده است. قلک می تواند حاوی سکه هایی از نوع
N باشد، برای هر نوع مقدار
Pi و وزن
Wi< /sub> شناخته می شوند یک سکه. حداقل و حداکثر پولی که می تواند در قلک باشد را پیدا کنید.
ورودی:
- خط اول شامل اعداد
E و
F (
\(1<=E<=F<=10000\)< /span>)؛
- در دوم - شماره N (\(1<=N<=500\));
- در سطرهای N بعدی - هر کدام دو عدد، Pi و Wi < / code>(\(1<=Pi<=50000\)، \(1<=Wi<=10000\ ) ).
همه اعداد اعداد صحیح هستند.
خروجی: دو عدد از هم جدا شده با یک فاصله نمایش داده می شود - حداقل و حداکثر مجموع. اگر قلک نمی تواند دقیقاً وزن تعیین شده را داشته باشد، مشروط بر اینکه با سکه هایی از انواع مشخص شده پر شده باشد، «این غیرممکن است.» را چاپ کنید.
نمونه‌ها
<سر>
| # |
ورودی |
خروجی |
<بدن>
| 1 |
1000 1100
2
1 1
5 2
|
100 250 |
| 2 |
1000 1010
2
6 3
2 2
|
10 16 |
| 3 |
1000 2000
1
10 3
|
این غیرممکن است. |