[BOJ] 4781 : 사탕 가게

#include <cstdio>
#include <cstring>
int n, m, m1, m2, dp[10001];
inline int max(int a, int b) { return a > b ? a : b; }
int main() {
    while (1) {
        scanf("%d %d.%d", &n, &m1, &m2);
        if (!n) break;
        
        memset(dp, 0, sizeof(dp));
        m = m1 * 100 + m2;

        int ans = 0;
        for (int i = 0, c, p; i < n; i++) {
            scanf("%d %d.%d", &c, &m1, &m2);
            p = m1 * 100 + m2;
            for (int j = p; j <= m; j++) {
                dp[j] = max(dp[j], dp[j - p] + c);
                ans = max(ans, dp[j]);
            }
        }
        
        printf("%d\n", dp[m]);
    }
    return 0;
}