1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 55;
int T, n, k;
inline LL func(LL a, LL b, LL c, LL d){
return (100 + a) * (100 + b) * (100 + c) * (100 + d);
}
struct Node{
LL a, b, c, d;
};
vector<Node> tp[N];
LL sa[N], sb[N], sc[N], sd[N];
LL ans;
void dfs(int i, LL A, LL B, LL C, LL D){
if(i == k){
ans = max(ans, func(A, B, C, D));
return;
}
if(func(A + sa[i+1], B + sb[i+1], C + sc[i+1], D + sd[i+1]) <= ans) return;
if(tp[i+1].empty()) dfs(i+1, A, B, C, D);
else{
for(auto &k : tp[i+1])
dfs(i+1, A + k.a, B + k.b, C + k.c, D + k.d);
}
}
int main(){
for(read(T); T; T--){
read(n, k);
ans = -1;
for(int i = 0; i <= 50; i++){
tp[i].clear();
sa[i] = sb[i] = sc[i] = sd[i] = 0;
}
for(int i = 1; i <= n; i++){
LL t, a, b, c, d; read(t, a, b, c, d);
tp[t].push_back((Node){a, b, c, d});
}
for(int i = 50; i >= 1; i--){
LL suma = 0, sumb = 0, sumc = 0, sumd = 0;
for(auto &k : tp[i]){
suma += k.a;
sumb += k.b;
sumc += k.c;
sumd += k.d;
}
sa[i] = sa[i+1] + suma;
sb[i] = sb[i+1] + sumb;
sc[i] = sc[i+1] + sumc;
sd[i] = sd[i+1] + sumd;
}
dfs(0, 0, 0, 0, 0);
printf("%lld\n", ans);
}
return 0;
}
|