USACO-T044: Stamps

/*
ID: mickyta1
TASK: stamps
LANG: C++
*/

#include <bits/stdc++.h>
using namespace std;

const int K = 200 + 5;
const int X = 2e6 + 5;

int arr[K], dp[X];

int main(){
    freopen("stamps.in", "r", stdin);
    freopen("stamps.out", "w", stdout);

    int n, limCnt;
    scanf("%d%d", &limCnt, &n);
    for(int i = 1; i <= n; ++i){
        scanf("%d", &arr[i]);
    }
    for(int x = 1; x <= 2e6; ++x){
        int mn = 1e9;
        for(int i = 1; i <= n; ++i){
            if(x >= arr[i]){
                mn = min(mn, 1 + dp[x - arr[i]]);
            }
        }
        dp[x] = mn;
        if(dp[x] > limCnt){
            cout << x - 1 << '\n';
            break;
        }
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}