D. Максимальная сумма
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Ахмед и Мостафа участвуют в соревнованиях по программированию уже много лет. Однажды их тренер Фегла попросил их решить одну непростую задачу. Конечно же, Ахмед справился, а Мостафа — нет.

Эта задача похожа на классическую задачу, но имеет другую структуру и ограничения.

В классической задаче дан массив целых чисел, требуется найти такой подмассив данного массива, что сумма чисел в нем максимальная возможная. Подмассив — последовательность из одного или нескольких подряд идущих элементов данного массива.

Но в данной задаче дано n маленьких массивов. Из них получается один большой массив — конкатенацией одного или нескольких экземпляров маленьких массивов (каждый маленький массив может встречаться в большом более одного раза). Большой массив задан в виде массива индексов (1-индексированных) маленьких массивов. Конкатенация должна быть выполнена в том же порядке, в котором числа записаны в массиве. После конкатенации на большом массиве решается описанная выше классическая задача.

Например, пусть маленькие массивы — {1, 6, -2}, {3, 3} и {-5, 1}. Индексы большого массива — {2, 3, 1, 3}. Так, после конкатенации большой массив будет {3, 3, -5, 1, 1, 6, -2, -5, 1}. В этом примере максимальная сумма равна 9.

Помогите Мостафе решить эту задачу.

Входные данные

В первой строке записано два целых числа n и m, где n — количество маленьких массивов (1 ≤ n ≤ 50), а m — количество индексов большого массива (1 ≤ m ≤ 250000). Далее следует n строк. Первое число в i-ой — целое число l, размер i-го маленького массива (1 ≤ l ≤ 5000). Далее следует l целых чисел, каждое из которых не меньше -1000 и не больше 1000. Последняя строка содержит m целых чисел — индексы большого массива. Вы должны конкатенировать маленькие массивы в этом порядке. Каждый индекс не меньше 1 и не больше n.

Маленькие массивы нумеруются от 1 до n в том же порядке, в котором они заданы во входных данных. Некоторые маленькие массивы могут не использоваться для построения большого массива.

Заметьте, что массив очень большой. Поэтому, если Вы попытаетесь построить его в явном виде, вы скорее всего превысите ограничения по времени и/или по памяти.

Выходные данные

Выведите одно число — наибольшую сумму на каком-либо подмассиве сформированного большого массива. Учтите, что подмассив суммирования не может быть пустым, то есть он должен включать в себя хотя бы один элемент.

Пожалуйста, не используйте спецификатор %lld для записи 64-х битовых чисел на С++. Рекомендуется использовать поток cout (также вы можете использовать спецификатор %I64d).

Примеры
Входные данные
3 4
3 1 6 -2
2 3 3
2 -5 1
2 3 1 3
Выходные данные
9
Входные данные
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
Выходные данные
8