|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||5||3||3||75.000%|
After five hours of intense battle, the final contest of XCPC is complete! Even though the standings were frozen during the last hour, it is obvious that there are just two contenders for the trophy, namely team A and team B. All other teams are ignored in this description from now on.
In XCPC, teams are ranked according to the most problems solved. Teams who solve the same number of problems are ranked by the least total penalty time. In case of a tie, team A is ranked above team B.
The number of problems solved and the penalty of both teams at the 4-hour mark are publicly known. You are responsible for showing the final standings at the closing ceremony, and you have been privately given a list of integers for each team. Each element of the list stands for a problem solved during the last hour, with its value denoting the amount of penalty the team will get for solving this problem.
At the closing ceremony, the standings will be unfrozen by revealing who solved which problems during the last hour, one by one. The following sequence of actions will be repeated until the standings are final:
You have control over which problem will be chosen for revealing in step 2 at every moment. Every time teams A and B exchange their ranks, spectators will be excited. Find the maximum number of times you can make this happen.
The input consists of two blocks of two lines each: a block for team A and a block for team B.
The first line of the i-th block contains two integers si and ti (1 ≤ si ≤ 100; 1 ≤ ti ≤ 30 000), denoting the number of problems solved and the penalty time received by the team during the first four hours.
The second line of the i-th block contains an integer ni (0 ≤ ni ≤ 100), denoting the number of problems solved by the team during the last hour, followed by ni integers ai,1, ai,2, . . . , ai,ni (241 ≤ ai,j ≤ 1000), denoting penalty times the team will receive for solving each of these problems.
Display the maximum number of times teams A and B can swap positions in the standings.
4 270 3 458 245 386 6 968 1 430
In the example test case, initially team B is at the top of the standings. First, team A is chosen twice. It is optimal to choose problems with penalties 245 and 386, in any order; then team A gets ahead of team B, with 6 problems and penalty 901. After that team B gets ahead of team A, with 7 problems and penalty 1398. Finally, team A gets ahead of team B again, with 7 problems and penalty 1359.