求助，#45被卡住了

rt，本人代码#45测试点1.05s被卡了，实在想不出怎么加速了，有大佬支招吗？（P.S.本人代码亲测厌氧，一开O2就是各种WA，TLE）

#include<bits/stdc++.h>
#define reg register ll
#define ll long long
using namespace std;
ll n,m,ans,price[25],use[2000005];
vector <ll> a,b;
inline ll read(){
    char ch=getchar();
    ll n=0,f=1;
    while(ch>'9'||ch<'0'){
        ch=getchar();
        if(ch=='-'){f=-1;}
    }
    while(ch>='0'&&ch<='9'){
        n=(n<<1)+(n<<3)+ch-'0';
        ch=getchar();
    }
    return n*f;
}
void dfs(ll l,ll r,ll sum,vector<ll> &k){
    if(sum>m){return;}
    if(l>r){
        k.push_back(sum);
        return;
    }
    dfs(l+1,r,sum+price[l],k);
    dfs(l+1,r,sum,k);
}
int main(){
    n=read(),m=read();
    ll mid=n>>1;
    for(reg i=1;i<=n;i++){
        price[i]=read();
    }
    dfs(1,mid,0,a);
    dfs(mid+1,n,0,b);
    sort(a.begin(),a.end());
    for(reg i=0;i<b.size();i++){
        ans+=(upper_bound(a.begin(),a.end(),m-b[i])-a.begin());
    }
    cout<<ans<<endl;
    return 0;
}