唐玄宗时国力达到鼎盛,因此在另一条时间线上有许多小政权来朝见唐玄宗。
由于人太多了, 唐玄宗选了n位亲信大臣。
其中第i位的大臣语言能力为ai,政治能力为bi,社交能力为ci,处理一个小政权的时间为Ti。
同时有K个小政权首领来朝见,第j个首领所需的语言能力为xj,政治能力为yj,社交能力为zj,时间为tj。(大臣处理能力)
共n+K+2行。
第1行输入n,
接下来n行,一行4个数,分别对应语言能力ai,政治能力bi,社交能力ci,处理一个小政权的时间Ti。
再输入K,
最后输入K行,同样一行4个数,分别对应所需的语言能力xj,政治能力yj,社交能力zj,时间tj。
共2行。
第一行由唐玄宗亲自处理事情的次数ans
第二行输出输出所需最少的时间T总,若某个首领所需的某个能力过大,则某大臣处理此事的时间为:“(Ti与ti之间较大者)∗1000”(不管哪个大臣处理此事,所需时间都为“(Ti与ti之间较大者)∗1000”)。一个大臣处理事情时不可再用。
2
1 1 1 9
3 3 3 4
3
1 3 2 3
2 2 2 1
3 3 1 2
0
12
2
1 1 1 10000
2 1 1 114514
2
1 1 100 1234
9 9 9 1
2
1235
3
1 1 1 1
2 2 2 2
3 3 3 3
3
2 100 1 10
1 1 1 10
999 999 999 150
2
160
0<n<105
0<K<105
0<ans<105
0<ai,bi,ci,Ti<105
0<xj,yj,zj,tj<105
A,B同时处理事情,A用时10,B用时20,则总时间为20