The Strongest Build

题意翻译

## 题目描述 Ivan正在玩另一个类似Rogue的电脑游戏。他控制着游戏里面的一个英雄，这个英雄有 $n$ 个装备槽，对于每个槽 $i$ 而言有 $c_i$ 个物品可以选择，第 $j$ 个物品会增加英雄 $a_{i,j}$ 的力量值。每个槽所对应的物品两两不同并按照可以增加的力量值升序排序，即： $a_{i,1}<a_{i,2}<\dots<a_{i,c_i}$ 对于每个装备槽，Ivan只能在它所对应的物品列表中至多选一个物品。选择的序列称作一个组合。 一个组合的力量值是组合中所包含的物品提升的力量值之和，然而有 $m$ 个两两不同的组合被游戏禁掉了，保证有至少一个组合没有被禁。 询问满足要求（不被禁）的组合的最大力量值为多少？如果有多个组合有相同的最大值，输出它们之中的任意一个即可。 ## 输入格式 第一行包含一个整数 $n(1 \leq n \leq 10)$ 代表装备槽的个数 接下来的 $n$ 行每一行代表第 $i$ 个装备槽可选的物品。每一行先是一个数字 $c_i(1 \leq c_i\leq 2 \times 10^5)$ 代表第 $i$ 个槽可选的物品个数，接下来是 $c_i$ 个整数 $a_{i,1},a_{i,2},\dots,a_{i,ci} (1 \leq a_{i,1}< a_{i,2} < \dots < a_{i,c_i} \leq 10^8 )$ $c_i$ 的总和不超过 $2 \times 10^5$ 下一行包含一个整数 $m(0 \leq m \leq 10^5)$ 代表被禁的组合个数 接下来的 $m$ 行每行有 $n$ 个数，代表每一个装备槽中的物品 ## 输出格式 一行 $n$ 个数，代表拥有最大力量值且满足要求（不被禁）的组合 translated by tw1ce

题目描述

Ivan is playing yet another roguelike computer game. He controls a single hero in the game. The hero has $ n $ equipment slots. There is a list of $ c_i $ items for the $ i $ -th slot, the $ j $ -th of them increases the hero strength by $ a_{i,j} $ . The items for each slot are pairwise distinct and are listed in the increasing order of their strength increase. So, $ a_{i,1} < a_{i,2} < \dots < a_{i,c_i} $ . For each slot Ivan chooses exactly one item. Let the chosen item for the $ i $ -th slot be the $ b_i $ -th item in the corresponding list. The sequence of choices $ [b_1, b_2, \dots, b_n] $ is called a build. The strength of a build is the sum of the strength increases of the items in it. Some builds are banned from the game. There is a list of $ m $ pairwise distinct banned builds. It's guaranteed that there's at least one build that's not banned. What is the build with the maximum strength that is not banned from the game? If there are multiple builds with maximum strength, print any of them.

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 1 \le n \le 10 $ ) — the number of equipment slots. The $ i $ -th of the next $ n $ lines contains the description of the items for the $ i $ -th slot. First, one integer $ c_i $ ( $ 1 \le c_i \le 2 \cdot 10^5 $ ) — the number of items for the $ i $ -th slot. Then $ c_i $ integers $ a_{i,1}, a_{i,2}, \dots, a_{i,c_i} $ ( $ 1 \le a_{i,1} < a_{i,2} < \dots < a_{i,c_i} \le 10^8 $ ). The sum of $ c_i $ doesn't exceed $ 2 \cdot 10^5 $ . The next line contains a single integer $ m $ ( $ 0 \le m \le 10^5 $ ) — the number of banned builds. Each of the next $ m $ lines contains a description of a banned build — a sequence of $ n $ integers $ b_1, b_2, \dots, b_n $ ( $ 1 \le b_i \le c_i $ ). The builds are pairwise distinct, and there's at least one build that's not banned.

输出格式

Print the build with the maximum strength that is not banned from the game. If there are multiple builds with maximum strength, print any of them.

输入输出样例

输入样例 #1

3
3 1 2 3
2 1 5
3 2 4 6
2
3 2 3
3 2 2

输出样例 #1

2 2 3

输入样例 #2

3
3 1 2 3
2 1 5
3 2 4 6
2
3 2 3
2 2 3

输出样例 #2

1 2 3

输入样例 #3

3
3 1 2 3
2 1 5
3 2 4 6
2
3 2 3
2 2 3

输出样例 #3

3 2 2

输入样例 #4

4
1 10
1 4
1 7
1 3
0

输出样例 #4

1 1 1 1