硬币2这题，TLE80！如何改？

[吴弈尘 (逆风而行)]

#include<bits/stdc++.h>
using namespace std;
int n,a[100005],c[100005],cnt,m;
int vis[1000005];
void dfs(int k,int sum){
    if (sum>m){  
        return;
    }
    if (k==n+1){
    	if(vis[sum]==0&&sum>0){
    		vis[sum]=1;
    		cnt++;
		}
		return;
	} 
    dfs(k+1,sum); 
	for(int i=1;i<=c[k];i++)     
    	dfs(k+1,sum+a[k]*i); 
}
int main(){
	cin>>n>>m; 
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&c[i]);
	}
 	dfs(0,0);              
	printf("%d",cnt); 
}

[冯泉清]

dfs?

[tyx (༺༺■̵̶̸̸̴̴̷̩͎̬͍̙͎͕͎̩͍͇̜͍̯̖͎̙͓̪͎͓̜̟͖͈̩͈̜̮̝̠̫̠͉̘̳̳̦͈͇̖͓̩͙̩̤͇̠̠̣͔͕̲͍̪̮̥̗̦͍͇͍͖̟͔͔̲̜̗̱̤̲̤̱̝̟͇̖͔̮͙̣͚̗̣̤̱͇͖̪͚͉̜̫̤̮͎̖̥͙̜̖̞̥͔͍̳͙̉̃̀͑͗͋̾̔̓̄̆̐̾͊̐̀̆̆̋̎̂̓̈̆̑͋͛̐̍̾̎͐̈́͋̌̾̓̌̂̿͗̂̂͗̊̇͛̾̋͂͒̉̿̾̽͛̈́̍̋͗̐͒͂̊̾͒̃̎̇͐̎̇́̅̈́͂̋̑͒́̓͆̅̓͌͗͋̏͒̽̒̉̂̔̒͆̊̐̀̈́̀͒̽̚̚ͅͅ҉再见，匹诺康尼_C++CodeIkun༻༻)]

用dp写，拜托