我用dp加单调数组做的；
单调数组q[i]记录的是从i往前到j（Sigema(a[i].v+..+a[j].v)恰好大于等于m）之间最大的那个数的序号
dp转移方程 dp[i]=max(dp[i-1],dp[last[i]-1]+a[q[head]].v);
#include\"stdio.h\"
#include\"string.h\"
#define N 50005
struct in{
	int p,v;
}a[N];
int last[N];
double sum[N];
int q[N];
double dp[N];
int main()
{
	int i,j,k,t;
	double now;
	int ii,jj,kk;
	int head,tail;
	double s;
	int n,m;
	scanf(\"%d\",&t);
	while(t--)
	{
		scanf(\"%d%d\",&n,&m);
		for(i=1;i<=n;i++)
			scanf(\"%d%d\",&a[i].p,&a[i].v);
		s=0;
		for(i=1;i<=n;i++)
		{
			s=s+a[i].p;
			if(s>=m)
				break;
		}
		if(i>n)
		{
			printf(\"0\\n\"); continue;
		}
		memset(dp,0,sizeof(dp));
		head=tail=0; q[0]=1;
		last[i]=1; sum[i]=s;
		for(j=2;j<=i;j++)
		{
			while(tail>=head&&a[j].v>=a[q[tail]].v)
			{
				tail--;
			}
			q[++tail]=j;
		}
		dp[i]=a[q[head]].v;
		for(j=i+1;j<=n;j++)
		{
			while(tail>=head&&a[j].v>=a[q[tail]].v)
			{
				tail--;
			}
			q[++tail]=j;
			if(a[j].p>=m)
			{
				last[j]=j;
				sum[j]=a[j].p;
			}
			else
			{
				now=sum[j-1]+a[j].p;
				for(k=last[j-1];;k++)
				{
					now=now-a[k].p;
					if(now<m)
						break;
				}
				last[j]=k;
				sum[j]=now+a[k].p;
			}
			while(q[head]<last[j])
				++head;
			dp[j]=dp[j-1];
			if(a[q[head]].v+dp[last[j]-1]>dp[j])
				dp[j]=dp[last[j]-1]+a[q[head]].v;
		}
		printf(\"%.0lf\\n\",dp[n]);
	}
}