CF75D.Big Maximum Sum

Ahmed and Mostafa used to compete together in many programming contests for several years. Their coach Fegla asked them to solve one challenging problem, of course Ahmed was able to solve it but Mostafa couldn't.

This problem is similar to a standard problem but it has a different format and constraints.

In the standard problem you are given an array of integers, and you have to find one or more consecutive elements in this array where their sum is the maximum possible sum.

But in this problem you are given n small arrays, and you will create one big array from the concatenation of one or more instances of the small arrays (each small array could occur more than once). The big array will be given as an array of indexes (1-based) of the small arrays, and the concatenation should be done in the same order as in this array. Then you should apply the standard problem mentioned above on the resulting big array.

For example let's suppose that the small arrays are {1, 6, -2}, {3, 3} and {-5, 1}. And the indexes in the big array are {2, 3, 1, 3}. So the actual values in the big array after formatting it as concatenation of the small arrays will be {3, 3, -5, 1, 1, 6, -2, -5, 1}. In this example the maximum sum is 9.

Can you help Mostafa solve this problem?

艾哈迈德和穆斯塔法曾一起参加过多年的多项编程竞赛。他们的教练费格拉给他们出了一道具有挑战性的问题，当然艾哈迈德成功解决了，但穆斯塔法却没能解出来。

本题与一道经典问题类似，但其格式和约束条件有所不同。

在经典问题中，你将获得一个整数数组，要求找出该数组中一个或多个连续元素，使得它们的和为所有可能连续子段和中的最大值。

而在本题中，你将获得 $n$ 个较小的数组；你需要通过拼接一个或多个这些小数组（每个小数组可重复使用多次）来构造一个大的数组。该大数组以小数组的索引（1-基索引）序列形式给出，且拼接顺序必须严格遵循该索引序列中各索引的出现顺序。随后，你需要对所得到的大数组应用上述经典问题。

例如，假设给定的小数组为 $\{1, 6, -2\}$、$\{3, 3\}$ 和 $\{-5, 1\}$，而大数组对应的索引序列为 $\{2, 3, 1, 3\}$。那么，按索引序列拼接后得到的实际大数组为 $\{3, 3, -5, 1, 1, 6, -2, -5, 1\}$。在此例中，最大子段和为 $9$。

你能帮助穆斯塔法解决这个问题吗？

The first line contains two integers n and m, n is the number of the small arrays (1 ≤ n ≤ 50), and m is the number of indexes in the big array (1 ≤ m ≤ 250000). Then follow n lines, the i-th line starts with one integer l which is the size of the i-th array (1 ≤ l ≤ 5000), followed by l integers each one will be greater than or equal -1000 and less than or equal 1000. The last line contains m integers which are the indexes in the big array, and you should concatenate the small arrays in the same order, and each index will be greater than or equal to 1 and less than or equal to n.

The small arrays are numbered from 1 to n in the same order as given in the input. Some of the given small arrays may not be used in big array.

Note, that the array is very big. So if you try to build it straightforwardly, you will probably get time or/and memory limit exceeded.

第一行包含两个整数 $n$ 和 $m$，其中 $n$ 表示小数组的个数（$1 \leq n \leq 50$），$m$ 表示大数组中的索引个数（$1 \leq m \leq 250000$）。接下来是 $n$ 行，第 $i$ 行以一个整数 $l$ 开头，表示第 $i$ 个小数组的长度（$1 \leq l \leq 5000$），随后是 $l$ 个整数，每个整数均满足 $-1000 \leq \text{值} \leq 1000$。最后一行包含 $m$ 个整数，表示大数组中所用到的小数组的索引；你需要按输入中给出的相同顺序拼接这些小数组，且每个索引值均满足 $1 \leq \text{索引} \leq n$。

小数组按输入顺序从 $1$ 到 $n$ 编号。给定的部分小数组可能在构造大数组时未被使用。

注意：该大数组规模极大。若尝试直接构建它，很可能会导致超时和/或内存超限。

Print one line containing the maximum sum in the big array after formatting it as described above. You must choose at least one element for the sum, i. e. it cannot be empty.

Please, do not use %lld specificator to write 64-bit integers in C++. It is preferred to use cout (also you may use %I64d).

输出一行，包含按上述方式格式化后的大型数组的最大和。您必须至少选择一个元素参与求和，即结果不能为空。

请注意，在 C++ 中不要使用 %lld 格式说明符来输出 64 位整数。推荐使用 cout（您也可以使用 %I64d）。