#P7608. [2018年杭电多校]Chopping hands

[2018年杭电多校]Chopping hands

Chopping hands

题目描述

Patrick Star wants to collect some cards.The number of cards' type is M M ,numbered from 1 1 to M M . There are N N card packs in the card shop: 1.The cost of ithi_{th} card pack is Ci C_{i} , note that Ci C_{i} may be negative. 2.The number of cards in ithi_{th} card pack is Di D_{i} . 3.The cards in all card packs are known,some types of card can appear in a pack more than once. 4.Each pack can be bought at most once; choose a nonempty subset of packs. Once Patrick Star gets an ith i_{th} type of card,he will regard Valuei,j Value_{i,j} as this card's value if the card is jthj_{th} got as the ithi_{th} type. (If you buy two packs [type 1,type 1,type 2] and [type 1,type 2,type 3],you will get value [$Value_{1,1}, Value_{1,2}, Value_{2,1}, Value_{1,3}, Value_{2,2}, Value_{3,1}]$) After Patrick Star choose some card packs bought,cost S S (may be negative too): If the chosen packs contain tit_i cards of type ii, their values of that type are exactly Valuei,1,…,Valuei,tiValue_{i,1},\ldots,Value_{i,t_i}, regardless of pack purchase order. Firstly, sort all received card values. We will get the median of the value as mid mid . (When the number of variables is an odd number, the value of the variable in the middle position is the median.when the number of variables is an even number, the median is the average of the 2 variable values in the middle position.) Then Patrick Star considers his satisfaction V V as V=2∗mid V = 2 * mid Patrick Star wants to know the maximum value of V−S V - S . Note that Patrick Star will buy at least one pack.

输入格式

The first line contain a integer TT (no morn than 10), the following is TT test case, for each test case : the first line contain two integers N and M. The second line contain N integers separated by spaces,C1,C2,…Cn C_{1},C_{2},\ldots C_{n} Then next N lines,the first integer of each line is Di D_{i} ,and the Di D_{i} integers after that represents the type of each card in i-th pack. Then next M lines,the first integer ti t_{i} of each line represents the number of times the i-th card appear in all packs,and the t integers after that,j-th integer represents Valuei,j Value_{i,j} . Limits: 1≤N≤21 1 \leq N \leq 21 1≤M≤200 1 \leq M \leq 200 −1,000,000≤Ci≤1,000,000 -1,000,000 \leq C_{i} \leq 1,000,000 $1 \leq D_{i} \leq 100 , \sum_{i=1}^{N}D_{i} \leq 100$ 0≤Valuei,j≤100,000,000 0 \leq Value_{i,j} \leq 100,000,000

输出格式

For each test case, please output an integer in a line represented the answer.It's clear that the answer is an integer.

样例输入 1

1
4 1
1 2 3 4
1 1
1 1
1 1
1 1
4 4 3 2 1

样例输出 1

7