Description
你有n种硬币，每种硬币有c个每个价值a，不同种硬币价值可能相同，
问你用这些硬币可以凑出1到m中多少种不同价值
Input
第一行一个整数t表示数据组数，每组数据第一行两个整数n,m，
接下来n行每行两个整数表示这种硬币的a和c
Output
对于每组数据输出一行可以凑出多少种不同价值
Sample Input
样例读入：
2
3 10
1 2
2 1
4 1
2 5
1 2
4 1
样例输出：
8
4
HINT
数据范围：
对于20%的数据，n<=10 a,m<=100 ,c<=10
对于50%的数据，n<=100 a,m<=1000 ,c<=100
对于100%的数据，n<=100 a,m<=100000, c<=1000, t<=3
01背包. 对c[i]进行二进制拆分优化.
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
const int maxN = 100;
const int maxM = (int)1e5;
int a[maxN];
int c[maxN];
int f[maxM + 1];
int main()
{
#ifndef ONLINE_JUDGE
freopen("coins.in", "r", stdin);
freopen("coins.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
int t;
for(cin >> t; t; t --)
{
int n, m;
cin >> n >> m;
for(int i = 0; i < n; i ++)
cin >> a[i] >> c[i];
memset(f, 0, sizeof(f));
f[0] = 1;
for(int i = 0; i < n; i ++)
{
for(int j = 0; (1 << j) <= c[i]; j ++)
{
c[i] -= (1 << j);
int tmp = a[i] * (1 << j);
for(int k = m; k >= tmp; k --)
if(f[k - tmp])
f[k] = 1;
}
for(int j = m; j >= c[i] * a[i]; j --)
if(f[j - c[i] * a[i]])
f[j] = 1;
}
int ans = 0;
for(int i = 1; i <= m; i ++)
if(f[i])
ans ++;
printf("%d
", ans);
}
}