设f[c[i]]表示：最后一个选的是颜色为c[i]的球的最大贡献。
可知f[c[i]]有以下三种转移得到：
f[c[i]]=f[c[j]]+u*a[i]（1<=j<i,c[j]=c[i]）
f[c[i]]=f[c[j]]+v*a[i]（1<=j<i,c[j]!=c[i]）
f[c[i]]=v*a[i]
所以我们如果能迅速得到最大的f[c[j]] (1<=j<i,c[j]!=c[i])的值，那么就可以实现复杂度：O(T n)。
记f[t1]为之前出现过的最大的f[c[i]]，f[t2]为之前出现过的次大的且t2!=t1的f[c[i]]。
这样就可以保证无论当前的c[i]为多少，t1,t2中至少有一个与c[i]不同。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,m,u,v,maxn;
int a[N],c[N],dp[N];
signed main(){
scanf("%lld%lld",&n,&m);for (register int i=1; i<=n; ++i) scanf("%lld",&a[i]);for (register int i=1; i<=n; ++i) scanf("%lld",&c[i]);while (m--){
maxn=0;scanf("%lld%lld",&u,&v);for (register int i=1; i<=n; ++i) dp[i]=-1e15;int t1=0,t2=0,ans=0;for (register int i=1; i<=n; ++i){
ans=max(v*a[i],dp[c[i]]+u*a[i]);if (c[i]!=t1) ans=max(ans,dp[t1]+v*a[i]);else ans=max(ans,dp[t2]+v*a[i]);if (ans>dp[t1]){
if (t1!=c[i]){
t2=t1;t1=c[i];}else t1=c[i];}else if (ans>dp[t2] && c[i]!=t1) t2=c[i];dp[c[i]]=max(dp[c[i]],ans);maxn=max(maxn,ans);}printf("%lld\n",maxn);}
return 0;
}