Прагнення об'єднатися
Група Acme Consulting відправила вас до нового технологічного парку, щоб підвищити динамізм, синергію та стійкість. Хоча ви не зовсім розумієте значення цих термінів, ви знаєте, як заробляти гроші, і саме це плануєте робити. Парк складається з 3×n рядків об'єктів. Кожен об'єкт містить стартап з певною вартістю. Ви плануєте збільшити їхню вартість шляхом злиття сусідніх стартапів, що дозволить вам здійснити вашу давню мрію відкрити власну мережу магазинів латте та буріто.
Згідно з антимонопольними законами, будь-яке злиття може включати лише два стартапи, і жоден стартап не може бути залучений у більше ніж одне злиття. Крім того, злиття можливе лише між стартапами, розташованими в сусідніх об'єктах (діагональ не враховується). Додана вартість, що генерується злиттям, дорівнює добутку вартостей двох залучених стартапів. Ви можете вирішити не залучати певний стартап у злиття, у такому випадку додана вартість не генерується. Ваша мета - знайти набір злиттів з максимальною загальною доданою вартістю. Наприклад, значення стартапів, показані на малюнку зліва, можуть бути оптимально злиті, як показано на малюнку справа, для загальної доданої вартості 171.
Вхідні дані
Перша строка кожного тестового випадку містить одне додатне число n ≤ 1000, що вказує на ширину рядків об'єктів. Далі йдуть три рядки, кожен з яких містить n додатних чисел (усі ≤ 100), що представляють значення кожного стартапу. Строка, що містить одне число 0, завершить введення.
Вихідні дані
Для кожного тестового випадку виведіть максимальну додану вартість, яку можна досягти шляхом злиттів для цього набору стартапів.