题目描述

小Q去商场购物，经常会遇到找零的问题。

小Q现在手上有n种不同面值的硬币，每种面值的硬币都有无限多个。

为了方便购物，小Q希望带尽量少的硬币，并且要能组合出1到m之间（包含1和m）的所有面值。

输入格式
第一行包含两个整数m和n。

接下来n行，每行一个整数，第 i+1 行的整数表示第 i 种硬币的面值。

输出格式
输出一个整数，表示最少需要携带的硬币数量。

如果无解，则输出-1。

数据范围

1≤n≤1001≤n≤100,
1≤m≤1091≤m≤109，
1≤硬币面值≤109

样例

输入样例：
20 4
1
2
5
10

输出样例：

5

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,m;
int a[N];
int main()
{
    cin>>m>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];

    sort(a,a+n);
    while(n>0&&a[n-1]>m)n--;
    a[n]=m+1;

    if(a[0]!=1)cout<<"-1"<<endl;
    else 
    {
        int res=0,s=0;//s是能凑到的钱数，k是当前硬币的数量 
        for(int i=0;i<n;i++)
        {
            int k=(a[i+1]-1-s+a[i]-1)/a[i];//一定要背住！！！！ 
            res+=k;//一定要背住！！！！
            s+=k*a[i];//一定要背住！！！！
        }

        cout<<res<<endl;
    }

    return 0;
}