思路：
每次放錢的時(shí)候，遵循兩個(gè)原則來尋找最優(yōu)方案：
1. 不能用面額小的組成面額大的
2. 所有方案中取最接近 C 的那個(gè)
就這樣一次次的放，放到?jīng)]錢為止。
注意，由于貨幣的數(shù)量較大，如果最優(yōu)方案可以執(zhí)行多次，那就一次過執(zhí)行完。
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 64
struct node 
{
int val, cnt;
};
struct node coin[MAX_N];
int N, C, best, best_idx, ans, need[MAX_N];
inline int min(int a, int b)
{
return a < b ? a : b;
}
int cmp(const void *a, const void *b)
{
return ((struct node *)a)->val - ((struct node *)b)->val;
}
inline int put(int idx, int val)
{
int n;
n = min(coin[idx].cnt, (C - val - 1) / coin[idx].val);
val += coin[idx].val * n;
if (coin[idx].cnt > n) {
if (!best || val + coin[idx].val < best) {
best = val + coin[idx].val;
best_idx = idx;
}
}
need[idx] = n;
return val;
}
inline int can()
{
int i, val;
best = val = 0;
for (i = N - 1; i >= 0; i--)
val = put(i, val);
return best;
}
inline void update()
{
int i, cnt;
cnt = 100000000;
need[best_idx]++;
for (i = N - 1; i >= best_idx; i--)
if (need[i])
cnt = min(cnt, coin[i].cnt / need[i]);
for (i = N - 1; i >= best_idx; i--)
coin[i].cnt -= cnt * need[i];
ans += cnt;
}
int main()
{
int i;
scanf("%d%d", &N, &C);
for (i = 0; i < N; i++)
scanf("%d%d", &coin[i].val, &coin[i].cnt);
qsort(coin, N, sizeof(coin[0]), cmp);
while (coin[N - 1].val >= C) {
ans += coin[N - 1].cnt;
N--;
}
while (can())
update();
printf("%d\n", ans);
return 0;
}