← 返回题目列表

Codeforces · 75/D

D. 大最大总和

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

艾哈迈德和穆斯塔法曾一起参加许多编程比赛多年。他们的教练费格拉要求他们解决一个具有挑战性的问题,艾哈迈德当然能够解决,但穆斯塔法却不能。

此问题与标准问题类似,但具有不同的格式和约束。

在标准问题中,您将得到一个整数数组,您必须在该数组中找到一个或多个连续元素,其中它们的总和是最大可能的总和。

但在这个问题中,您将获得 n 个小数组,您将通过串联一个或多个小数组实例来创建一个大数组(每个小数组可能出现多次)。大数组将作为小数组的索引数组(从 1 开始)给出,并且应按照与该数组中相同的顺序进行串联。然后,您应该将上面提到的标准问题应用到生成的大数组上。

例如,假设小数组为 {1, 6, -2}、{3, 3} 和 {-5, 1}。大数组中的索引是{2,3,1,3}。因此,将大数组格式化为小数组的串联后,大数组中的实际值将是 {3, 3, -5, 1, 1, 6, -2, -5, 1}。在此示例中,最大总和为 9。

你能帮助Mostafa解决这个问题吗?

输入

第一行包含两个整数 n 和 m,n 是小数组的数量 (1 ≤ n ≤ 50),m 是大数组中的索引数量 (1 ≤ m ≤ 250000)。然后是 n 行,第 i 行以一个整数 l 开头,即第 i 个数组的大小(1 ≤ l ≤ 5000),后面跟着 l 个整数,每个整数大于或等于 -1000 且小于或等于 1000。最后一行包含 m 个整数,它们是大数组中的索引,应按相同顺序连接小数组,每个索引将大于或等于 1 且小于或等于名词

小数组按照输入中给出的顺序从 1 到 n 编号。某些给定的小数组可能无法在大数组中使用。

请注意,该数组非常大。因此,如果您尝试直接构建它,您可能会超出时间或/和内存限制。

输出

按照上述方式格式化后,打印包含大数组中最大和的一行。您必须至少选择一个元素作为总和,i。 e.它不能为空。

请不要使用 %lld 说明符在 C++ 中写入 64 位整数。最好使用 cout (也可以使用 %I64d)。

示例

输入 #1

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

输出 #1

9

输入 #2

6 1
4 0 8 -3 -10
8 3 -2 -5 10 8 -9 -5 -4
1 0
1 -3
3 -8 5 6
2 9 6
1

输出 #2

8