这是一篇 $corner$ $case$ 的题解。

我们发现思路显然是从大到小枚举每一种数字，然后让它在满足前面所有限制都满足的时候尽可能大。

然后我们发现这样写很困难，于是我们不妨考虑分治，课上思路已经讲了，就不再赘述。

然后我重点说一下一些细节。

首先我们设函数 $solve(l,r,bes,eds)$ 表示区间 $[l,r]$，我在打 $l$ 之前的血量为 $bes$ ，然后打完 $r$ 之后的血量为 $eds$ 。注意这里不算打完 $r$ 后回的 $b$ 点血量。

我们找到区间最大值，然后我们判断如果前面所有的点都不花血量，一直攒血能不能攒到满血。

如果能

我们再看看我这里能不能把血量在最大值处都花完。具体判断方法是，我们看看如果后面所有的点都不花血量，能不能使得最后的血量不小于 $eds$，对于两种情况分别讨论即可。

然后我们再分别去跑 $[l,mxid-1]$ ，$[mxid+1,r]$

如果不能

我们显然一直攒血到最大值点是最优秀的，于是我们只去递归跑 $[mxid+1,r]$ ，当然前面的情况也需要分别判断

CODE

#include<bits/stdc++.h>
//#define int long long
using namespace std;
int a[1000005],Log[1000005];
int st[1000005][21];
long long ans=0;int s,b,n;
inline int query(int l,int r){
	int K=Log[r-l+1];
	if(a[st[l][K]]>=a[st[r-(1<<K)+1][K]])return st[l][K];
	else return st[r-(1<<K)+1][K];
}
void solve(int l,int r,int bes,int eds){
	if(l>r)return;
	int mxid=query(l,r);
	int cnt=mxid-l;
	if(cnt*1ll*b+bes>=s){
		int cnt2=r-mxid;
		if(cnt2*1ll*b<eds){
			ans+=(s+cnt2*1ll*b-eds)*1ll*a[mxid];
			solve(l,mxid-1,bes,max(s-b,0));
			solve(mxid+1,r,min(s*1ll,s-(s+cnt2*1ll*b-eds)+b),eds);
		}else{
			ans+=s*1ll*a[mxid];
			solve(l,mxid-1,bes,max(s-b,0));
			solve(mxid+1,r,min(b,s),eds);
		}
	}else{
		int cnt2=r-mxid;
		if(cnt2*1ll*b<eds){
			ans+=(cnt*1ll*b+bes+cnt2*1ll*b-eds)*1ll*a[mxid];
			solve(mxid+1,r,min(s*1ll,cnt*1ll*b+bes-(cnt*1ll*b+bes+cnt2*1ll*b-eds)+b),eds);
			return;
		}
		else{
			ans+=(cnt*1ll*b+bes)*1ll*a[mxid];
			solve(mxid+1,r,min(b,s),eds);
		}
	}
}inline int read(){
	int x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x;
}
int main(){
//	freopen("打游戏ex_.in","r",stdin);
	int T=read();//scanf("%d",&T);
	for(int i=2; i<=500000; i++)Log[i]=Log[i>>1]+1;
	while(T--){
		s=read(),b=read(),n=read();
		for(int i=1; i<=n; i++)a[i]=read(),st[i][0]=i;
		for(int j=1; j<=Log[n]; j++)
			for(int i=1; i<=n; i++){
				if(a[st[i][j-1]]>=a[st[i+(1<<j-1)][j-1]])st[i][j]=st[i][j-1];
				else st[i][j]=st[i+(1<<j-1)][j-1];
			}
		ans=0;solve(1,n,s,0);
		printf("%lld\n",ans);
	}
	return 0;
}/*
1
10 2 10
4 3 6 6 9 10 1 3 4 5
*/