A30844.【动态规划】【背包】猪猪储蓄罐

入门

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

小林决定存钱准备买房。但是他平时花钱如流水,所以也存不出什么钱。因此他决定从最小最小的零钱开始存。而小林为了不让自己乱用钱,决定用那种不砸破拿不出钱的猪猪储蓄罐。但是在砸碎储蓄罐之前,小林还是不能知道自己到底有多少钱。请帮他计算他储蓄罐里最少有多少钱。只要知道最少就好了,好让他可以知道离渺茫的房子还差多少钱。

输入格式

第1行两个正整数E和F(1 <=E <=F <=10000),表示空的猪猪储蓄罐的重量和存满了钱的重量,中间用一个空格隔开。

接下来一行一个正整数N(1 <=N <=500), 表示有N种硬币。


再接下来N行数据,每行有两个正整数P、W(1 <=P <=50000, 1 <=W <=10000), P表示每种硬币的价值,W是每种硬币的重量,中间用一个空格隔开。

输出格式

输出重量F的最小价格,如果能,则输出一行字符串“The minimum amount of money in the piggy-bank is X.”, X是最小的价值;否则,输出"This is impossible."注意字符串严格匹配。

输入输出样例

  • 输入#1

    10 110
    2
    1 1
    30 50

    输出#1

    The minimum amount of money in the piggy-bank is 60.
    
首页