sbw太神啦orz
首先N<=20可以直接暴搜
然后玄学剪枝可以过18个点
那么N<=40的时候，就把它拆成两半分别暴搜，再用dp拼起来
对于前半段，设f[i][j]是开始高度为i，获得金币为j的方案数；对于后半段，设g[i][j]是结束高度为i，获得金币为j的方案数（离散化一下高度）
然而V<=4e7，并不能直接记
但其实每一段最多只有$2^{20}$种金币数，状压一下每一位选不选，再预处理出来这样的金币数是多少
然后统计答案，$ans=\sum{g[i][j]*f[k][l]}，i>k,v[j]+v[l]>=M$
给f做一个前缀和，给每个状态按v排序，可以$O(n*2^{n/2})$统计答案
然后会MLE，注意到对于每种状态其实每个开始高度/结束高度 都只有选或者不选，做个前缀和最多也只有20
把int改成unsigned char 就行了(逃
#include<bits/stdc++.h>
#define pa pair<int,int>
#define CLR(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=,maxs=(<<)+;
inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
}
int H[maxn],N,M,v1[maxs],v2[maxs],rk1[maxs],rk2[maxs];
unsigned char f[][maxs],g[][maxs];
void dfs1(int x,int tar,int h,int y){
if(x>tar) return;
dfs1(x+,tar,h,y);
if(H[x]>h) f[H[x]][y|(<<(x-))]++,dfs1(x+,tar,H[x],y|(<<(x-)));
}
void dfs2(int x,int tar,int h,int y){
if(x<tar) return;
dfs2(x-,tar,h,y);
if(H[x]<h) g[H[x]][y|(<<(x-tar))]++,dfs2(x-,tar,H[x],y|(<<(x-tar)));
} inline bool cmp1(int a,int b){return v1[a]<v1[b];}
inline bool cmp2(int a,int b){return v2[a]<v2[b];}
int main(){
// freopen("62.in","r",stdin);
// freopen("62.out","w",stdout);
int i,j,k;
N=rd(),M=rd();
for(i=;i<=N;i++){
rk1[i]=H[i]=rd(),rk2[i]=rd();
}
sort(rk1+,rk1+N+);
int t=unique(rk1+,rk1+N+)-rk1-;
for(i=;i<=N;i++)
H[i]=lower_bound(rk1+,rk1+t+,H[i])-rk1;
int m=N>>;
int n1=(<<m)-,n2=(<<(N-m))-;
dfs1(,m,,);
dfs2(N,m+,,); f[][]=;g[t+][]=;
for(i=;i<=t;i++){
for(j=;j<=n1;j++)
f[i][j]+=f[i-][j];
}
for(i=;i<=n1;i++){
for(j=;j<=m;j++)
if((i>>(j-))&) v1[i]+=rk2[j];
}for(i=;i<=n2;i++){
for(j=;j<=N-m;j++)
if((i>>(j-))&) v2[i]+=rk2[j+m];
}
for(i=;i<=n1;i++) rk1[i]=i;
for(i=;i<=n2;i++) rk2[i]=i;
sort(rk1+,rk1+n1+,cmp1);
sort(rk2+,rk2+n2+,cmp2);
ll ans=;
for(i=;i<=t+;i++){
ll s=;
for(j=,k=n1;j<=n2;j++){
for(;k>=&&v1[rk1[k]]+v2[rk2[j]]>=M;k--)
s+=f[i-][rk1[k]];
ans+=s*g[i][rk2[j]];
}
}
printf("%lld\n",ans);
return ;
}