Problem link: http://lightoj.com:81/volume/problem/1233

My solution:

#include <bits/stdc++.h>
#define mx 100005
using namespace std;
vector<int> dp[105];
int a[105];
int c[105];
bool mark[mx];
int n, m;
void coin_change(int i, int sum){
	mark[sum] = true;
	if(sum == m || i == n || dp[i][sum] != -1){
		return;
	}
	int j;
	for(j = 0; j <= c[i] and sum + j * a[i] <= m; j++){
		coin_change(i + 1, sum + j * a[i]);
		dp[i + 1][sum + j * a[i]] = 1;
		//mark[sum + j * a[i]] = true;
	}
}
int main(){
	//freopen("in.txt", "r", stdin);
	int t, tc, i, cnt, j;
	scanf("%d", &tc);
	for(t = 1; t <= tc; t++){
		scanf("%d %d", &n, &m);
		for(i = 0; i < n; i++){
			scanf("%d", &a[i]);
		}
		for(i = 0; i < n; i++){
			scanf("%d", &c[i]);
		}
		for(i = 0; i <= n; i++){
			for(j = 0; j <= m; j++){
				dp[i].push_back(-1);
			}
		}
		memset(mark, false, sizeof mark);
		coin_change(0, 0);
		cnt = 0;
		for(i = 1; i <= m; i++){
			if(mark[i]) cnt++;
		}
		printf("Case %d: %d\n", t, cnt);
		for(i = 0; i <= n; i++){
			dp[i].clear();
		}
	}
	return 0;
}