艾哈迈德和穆斯塔法曾一起参加许多编程比赛多年。他们的教练费格拉要求他们解决一个具有挑战性的问题,艾哈迈德当然能够解决,但穆斯塔法却不能。
此问题与标准问题类似,但具有不同的格式和约束。
在标准问题中,您将得到一个整数数组,您必须在该数组中找到一个或多个连续元素,其中它们的总和是最大可能的总和。
但在这个问题中,您将获得 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