记录编号	593433	评测结果	AAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[USACO23 Jan Platinum] Mana Collection	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	6.497 s
提交时间	2024-09-01 13:41:46	内存使用	56.35 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define fi first
#define in inline
#define se second
#define mp make_pair
#define pb push_back
const int N = 20,M = 1<<19;
const ll inf = 1e18;

ll read(){
	ll x = 0,f = 1;char c = getchar();
	for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
	for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
	return x * f;
}


int n,m,q;
ll d[N][N],s[M],f[M][N];


struct line{
	ll k,b = -inf;
	line(ll k,ll b):k(k),b(b){}
	line(){}
	ll val(ll x){return k * x + b;}
};
bool cmp(line a,line b,ll x){return a.val(x) > b.val(x);}


int root[N];
struct LiChao_tree{
	line mi[M<<2];int ls[M<<2],rs[M<<2],cnt;
	line ask(line a,line b,ll x){return cmp(a,b,x) ? a : b;}
	void modify(int &p,int l,int r,line x){
		if(l > r)return;
		if(!p)mi[p = ++cnt] = x;
		int mid = l + r >> 1;
		if(cmp(x,mi[p],mid))swap(x,mi[p]);
		if(cmp(x,mi[p],l))modify(ls[p],l,mid,x);
		if(cmp(x,mi[p],r))modify(rs[p],mid+1,r,x);
	}
	line cal(int p,int l,int r,int x){
		if(!p)return {0,-inf};
		if(l == r)return mi[p];
		int mid = l + r >> 1;
		if(x <= mid)return ask(cal(ls[p],l,mid,x),mi[p],x);
		else return ask(cal(rs[p],mid+1,r,x),mi[p],x); 
	}
}t;


ll c[N];
int main(){
	freopen("falishouji.in","r",stdin);
	freopen("falishouji.out","w",stdout);
	n = read(),m = read();
	for(int i = 1;i <= n;i++)c[i] = read();
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= n;j++)if(i != j)d[i][j] = inf;
	for(int i = 1;i <= m;i++){
		int x = read(),y = read();ll z = read();
		d[x][y] = min(d[x][y],z); 
	}
	for(int k = 1;k <= n;k++)
		for(int i = 1;i <= n;i++)
			for(int j = 1;j <= n;j++)d[i][j] = min(d[i][j],d[i][k] + d[k][j]);
	for(int i = 0;i < (1 << n);i++)
		for(int j = 1;j <= n;j++)f[i][j] = inf;
	for(int i = 1;i < (1 << n);i++){
		for(int j = 1;j <= n;j++)
			if(i >> j - 1 & 1)s[i] += c[j];
		for(int j = 1;j <= n;j++){
			if(!(i >> j - 1 & 1))continue;
			int now = i - (1 << j - 1);
			if(!now)f[i][j] = 0;
			for(int k = 1;k <= n;k++){
				if(!(now >> k - 1 & 1) || d[k][j] == inf)continue;
				f[i][j] = min(f[i][j],f[now][k] + s[now] * d[k][j]);
			}
			t.modify(root[j],1,(int)1e9,{s[i],-f[i][j]});
		}
	}
	q = read();
	for(int i = 1;i <= q;i++){
		ll s = read(),x = read();
		printf("%lld\n",t.cal(root[x],1,(int)1e9,s).val(s));
	}

	return 0;

}