题解

（请在此补充题目的中文题解与思路描述。）

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
   int s=0, w=1;
   char ch = getchar();
   while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar();}
   while (ch >= '0' && ch <= '9') s = (s<<3)+(s<<1) + ch - '0', ch = getchar();
   return s * w;
}
inline void put(int x){
   if(!x)putchar('0');
   if(x<0)putchar('-'),x=-x;
   int num(0);char c[66];
   while(x)c[++ num]=x%10+48,x/=10;
   while(num)putchar(c[num --]);
   return (void)(putchar('\n'));
}
int n,m,k,a[100005],s[100005],c[100005],x[100005],ask[100005],ans[2000005],N=1e5,cnt[100005],tot;
struct node{
	int w,id;
	bool friend operator<(node a,node b){
		return a.w<b.w;
	}
};priority_queue<node>q;
vector<node>tmp[100005];
signed main(){
	n=read(),m=read(),k=read();
	for(int i=1;i<=n;i++){
		a[i]=read(),s[i]=read(),c[i]=read(),x[i]=read();
		if(!x[i])tmp[N].push_back({a[i]+s[i],i});
		else tmp[min(N,(c[i]-1)/x[i]+1)].push_back({a[i]+s[i],i});
	}
	for(int i=1;i<=k;i++)ask[i]=read();
	for(int i=N;i>=1;i--){
		for(auto v:tmp[i])q.push(v);
		int res=m;vector<node>tp;
		while(res&&q.size()){
			int t=q.top().id;q.pop();
			if(!cnt[t]){
				cnt[t]++,res--;
				if(c[t]>1)q.push({a[t],t});
			}
			else{
				int now=min(c[t]-(i-1)*x[t]-cnt[t],res);
				res-=now,cnt[t]+=now;
				if(cnt[t]<c[t])tp.push_back({a[t],t});
			}
		}
		for(auto v:tp)q.push(v);
	}
	for(int i=1;i<=n;i++){
		if(cnt[i])ans[++tot]=a[i]+s[i];
		for(int j=2;j<=cnt[i];j++)ans[++tot]=a[i];
	}
	sort(ans+1,ans+tot+1),reverse(ans+1,ans+tot+1);
	for(int i=1;i<=tot;i++)ans[i]+=ans[i-1];
	for(int i=1;i<=k;i++)put(ans[min(tot,ask[i]*m)]);
}