小Hi在帮助钢铁侠开发新的盔甲。这套新盔甲一共包含M种武器插槽，其中第i种插槽有Ci个。每个插槽最多安装一个武器模块。
小Hi一共准备了N个武器模块，编号1~N。每个武器模块都有三个参数Vi, Pi和Ti。其中Vi描述了第i个模块的威力，Pi描述了该模块可以安装在哪种插槽中，Ti描述了该模块是否需要JARVIS的支持(1代表需要JARVIS支持，0代表不需要JARVIS支持)。
由于JARVIS的运算能力有限，它最多能同时支持K个武器模块。
现在小Hi想知道，如何装备武器模块才能使总威力最大，同时需要JARVIS支持的模块不超过K个。
输入
输入第一行包含一个整数T，代表测试数据的组数。
对于每组测试数据：
第一行包含三个整数N，M和K。
以下N行每行包含三个整数Vi, Pi和Ti。
最后一行包含M个整数，C1, C2, ... CM。
对于30%的数据, T <= 20, N <= 100, M <= 10, K <= 100
对于另70%的数据, T <= 2, 1 <= N <= 105, 1 <= M <= 104, 0 <= K <= 105
对于100%的数据, 1 <= Vi <= 100, 1 <= Pi <= M, 0 <= Ti <= 1, 0 <= Ci <= 100
输出
输出最大的总威力。
-------------------------------------------------------------------------------------------------------
开始想的是分组背包，没有考虑到这样做的话复杂度是10w*10w肯定超时。。
贪心，对于某类物体，首先计算不用javis的最大威力，然后计算他付出1个javis的最大、次大……收益是多少。
收益的计算是个“y”的形状。“y”中的“/”是不需要javis的前Ci个的升序排列，"y"中的""是需要javis的降序排列。收益就是"y"中的">"。
对所有的这些收益排个序，累加前k大的收益就好了
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10100; //m个物体
vector<int> weapons[N][2];
int incomes[N*10],income_cnt;
bool cmp(int a,int b){return a>b;}
int main(){
int t,tmpv,tmpp,tmpt,lim; for(cin>>t;t--;){
int n,m,K; cin>>n>>m>>K;
for(int i=0;i<m;i++) {
weapons[i][0].clear();
weapons[i][1].clear();
}
for(int i=0;i<n;i++) {
scanf("%d%d%d",&tmpv,&tmpp,&tmpt);
weapons[tmpp-1][tmpt].push_back(tmpv);
}
income_cnt = 0;
long long ans = 0;
for(int i=0;i<m;i++){
scanf("%d",&lim);
if(lim>0){
while(weapons[i][0].size()<lim) weapons[i][0].push_back(0);
std::sort(weapons[i][0].begin(),weapons[i][0].end(),cmp);
std::sort(weapons[i][1].begin(),weapons[i][1].end(),cmp);
for(int j=0;j<lim;j++) ans+=weapons[i][0][j];
for(int j=lim-1;j>=0;j--){
int k = lim-j-1; if(k>=weapons[i][1].size()) break;
int income = weapons[i][1][k]-weapons[i][0][j];
if(income<=0) break;
incomes[income_cnt++] = income;
}
}
}
std::sort(incomes,incomes+income_cnt,cmp);
lim = std::min(income_cnt,K);
for(int i=0;i<lim;i++) ans+=incomes[i];
printf("%lld
",ans);
}
return 0;
}