[POJ] 1276 Cash Machine.cpp

#include <cstdio>
#include <algorithm>
using namespace std;

int dp[100005];

int main()
{
    int cash, N, n[11], D[11];
    while (scanf("%d %d", &cash, &N) != EOF) {
        // Input
        for (int i = 0; i < N; ++i)
            scanf("%d %d", &n[i], &D[i]);
        // Initial
        fill(dp, dp+cash+1, 0);
        // Knapsack
        for (int i = 0; i < N; ++i) {
            int left = n[i];
            while (left > 10) {
                for (int j = 1; j <= left; left -= j, j *= 2)
                    for (int k = cash; k - D[i]*j >= 0; --k)
                        dp[k] = max(dp[k], dp[k-D[i]*j] + D[i]*j);
            }
            for (int j = 0; j < left; ++j)
                for (int k = cash; k - D[i] >= 0; --k)
                    dp[k] = max(dp[k], dp[k-D[i]] + D[i]);
        }
        printf("%d\n", dp[cash]);
    }
}