Стремление к слиянию
Acme Consulting Group отправила вас в новый технологический парк для повышения динамичности, синергии и устойчивости. Вы не уверены, что означают все эти термины, но вы точно знаете, как зарабатывать деньги, и намерены этим заняться. Парк состоит из 3×n рядов объектов. В каждом объекте находится стартап с определенной стоимостью. Путем содействия слияниям между соседними стартапами, вы хотите увеличить их стоимость, чтобы осуществить свою давнюю мечту — открыть сеть кофеен и буррито.
Из-за антимонопольных законов каждое слияние может включать только два стартапа, и ни один стартап не может участвовать более чем в одном слиянии. Более того, два стартапа могут объединиться только если они находятся в соседних объектах (диагональ не учитывается). Добавленная стоимость, получаемая от слияния, равна произведению стоимостей двух участвующих стартапов. Вы можете решить не вовлекать стартап в слияние, в этом случае добавленная стоимость не генерируется. Ваша цель — найти набор слияний с максимальной общей добавленной стоимостью. Например, значения стартапов, показанные на рисунке слева, могут быть оптимально объединены, как показано на рисунке справа, для общей добавленной стоимости 171.
Входные данные
Первая строка каждого тестового случая содержит одно положительное число n ≤ 1000, указывающее ширину сетки объектов. Далее следуют три строки, каждая из которых содержит n положительных целых чисел (все ≤ 100), представляющих значения каждого стартапа. Строка, содержащая одно число 0, завершает ввод.
Выходные данные
Для каждого тестового случая выведите максимальную добавленную стоимость, достижимую через слияния для данного набора стартапов.