← 返回题目列表

Codeforces · 1574/D

D. 最强的构建

中文机器翻译题面 查看原题

Ivan 正在玩另一款 Roguelike 电脑游戏。他在游戏中控制单个英雄。英雄有 $$$n$$$ 装备槽。第 $$$i$$$ 个插槽有一个 $$$c_i$$$ 物品列表,其中第 $$$j$$$ 会增加英雄强度 $$$a_{i,j}$$$。每个插槽的物品都是成对不同的,并按其强度增加的升序列出。所以,$$$a_{i,1} < a_{i,2} < \dots < a_{i,c_i}$$$。

对于每个插槽,Ivan 只选择一个项目。令第 $$$i$$$ 个槽位的所选项目为相应列表中的第 $$$b_i$$$ 个项目。选择序列 $$$[b_1, b_2, \dots, b_n]$$$ 称为构建。

构建的强度是其中项目的强度增加的总和。一些构建被禁止出现在游戏中。有一个 $$$m$$$ 成对不同的禁止版本列表。保证至少有一个版本未被禁止。

未被游戏禁止的最大强度的体型是什么?如果存在多个具有最大强度的构建,则打印其中任何一个。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10$$$) — 设备槽数。

接下来的 $$$n$$$ 行的第 $$$i$$$ 行包含第 $$$i$$$ 个插槽的项目描述。首先,一个整数 $$$c_i$$$ ($$$1 \le c_i \le 2 \cdot 10^5$$$) — 第 $$$i$$$ 个插槽的项目数。然后 $$$c_i$$$ 整数 $$$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$$$)。

$$$c_i$$$ 的总和不超过 $$$2 \cdot 10^5$$$。

下一行包含一个整数 $$$m$$$ ($$$0 \le m \le 10^5$$$) — 被禁止的版本数。

接下来的 $$$m$$$ 行中的每一行都包含对禁止构建的描述 - 一系列 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le c_i$$$)。

构建是成对不同的,并且至少有一个构建未被禁止。

输出

打印未被游戏禁止的最大强度的构建。如果存在多个具有最大强度的构建,则打印其中任何一个。

示例

输入 #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