Ахмед и Мостафа участвуют в соревнованиях по программированию уже много лет. Однажды их тренер Фегла попросил их решить одну непростую задачу. Конечно же, Ахмед справился, а Мостафа — нет.
Эта задача похожа на классическую задачу, но имеет другую структуру и ограничения.
В классической задаче дан массив целых чисел, требуется найти такой подмассив данного массива, что сумма чисел в нем максимальная возможная. Подмассив — последовательность из одного или нескольких подряд идущих элементов данного массива.
Но в данной задаче дано n маленьких массивов. Из них получается один большой массив — конкатенацией одного или нескольких экземпляров маленьких массивов (каждый маленький массив может встречаться в большом более одного раза). Большой массив задан в виде массива индексов (1-индексированных) маленьких массивов. Конкатенация должна быть выполнена в том же порядке, в котором числа записаны в массиве. После конкатенации на большом массиве решается описанная выше классическая задача.
Например, пусть маленькие массивы — {1, 6, -2}, {3, 3} и {-5, 1}. Индексы большого массива — {2, 3, 1, 3}. Так, после конкатенации большой массив будет {3, 3, -5, 1, 1, 6, -2, -5, 1}. В этом примере максимальная сумма равна 9.
Помогите Мостафе решить эту задачу.
Выходные данные
Выведите одно число — наибольшую сумму на каком-либо подмассиве сформированного большого массива. Учтите, что подмассив суммирования не может быть пустым, то есть он должен включать в себя хотя бы один элемент.
Пожалуйста, не используйте спецификатор %lld для записи 64-х битовых чисел на С++. Рекомендуется использовать поток cout (также вы можете использовать спецификатор %I64d).