#P7608. [2018年杭电多校]Chopping hands
[2018年杭电多校]Chopping hands
Chopping hands
题目描述
Patrick Star wants to collect some cards.The number of cards' type is ,numbered from to . There are card packs in the card shop: 1.The cost of card pack is , note that may be negative. 2.The number of cards in card pack is . 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 type of card,he will regard as this card's value if the card is got as the 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 (may be negative too): If the chosen packs contain cards of type , their values of that type are exactly , regardless of pack purchase order. Firstly, sort all received card values. We will get the median of the value as . (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 as Patrick Star wants to know the maximum value of . Note that Patrick Star will buy at least one pack.
输入格式
The first line contain a integer (no morn than 10), the following is test case, for each test case : the first line contain two integers N and M. The second line contain N integers separated by spaces, Then next N lines,the first integer of each line is ,and the integers after that represents the type of each card in i-th pack. Then next M lines,the first integer 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 . Limits: $1 \leq D_{i} \leq 100 , \sum_{i=1}^{N}D_{i} \leq 100$
输出格式
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