设有n 种不同面值的硬币，各硬币的面值存于数组T［1:n］中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins［1:n］中。 对于给定的1≤n≤10，硬币面值数组T和可以使用的各种面值的硬币个数数组Coins，以及钱数m，0≤m≤20001，编程计算找钱m的最少硬币数。

Input

第一行中只有1 个整数给出n的值,第2 行起每行2 个数，分别是T[j]和Coins[j]。最后1 行是要找的钱数m。

Output

最少硬币数,无解时输出-1

Sample Input

31 32 35 318

Sample Output

5

#include <iostream>

#include <cstring>

using namespace std;

int m,n,T[15],Coins[15],dp[20005];

void DP(int Sum,int num)

{

    int i;

    for(i=m;i>=Sum;i--)

    {

        dp[i]=min(dp[i],dp[i-Sum]+num);

    }

}

void solve()

{

    int i,j;

    for(i=0;i<n;i++)

    {

        j=1;

        while(1)

        {

            if(Coins[i]-j<=0)

            {

                DP(Coins[i]*T[i],Coins[i]);

                break;

            }

            Coins[i]-=j;

            DP(j*T[i],j);

            j*=2;

        }

    }

}

int main()

{

    int i;

    while(cin>>n)

    {

        for(i=0;i<n;i++)

        {

            cin>>T[i]>>Coins[i];

        }

        cin>>m;

        for(i=0;i<=m;i++)

        {

            dp[i]=100000000;

        }

        dp[0]=0;

        solve();

        if(dp[m]!=100000000)

        {

        cout<<dp[m]<<endl;

        }

        else

        {

            cout<<"-1"<<endl;

        }

    }

    return 0;

}