Прагнення об'єднатися

Група Acme Consulting відправила вас до нового технологічного парку, щоб підвищити динамізм, синергію та стійкість. Хоча ви не зовсім розумієте значення цих термінів, ви знаєте, як заробляти гроші, і саме це плануєте робити. Парк складається з 3 \times n рядків об'єктів. Кожен об'єкт містить стартап з певною вартістю. Ви плануєте збільшити їхню вартість шляхом злиття сусідніх стартапів, що дозволить вам здійснити вашу давню мрію відкрити власну мережу магазинів латте та буріто.

Згідно з антимонопольними законами, будь-яке злиття може включати лише два стартапи, і жоден стартап не може бути залучений у більше ніж одне злиття. Крім того, злиття можливе лише між стартапами, розташованими в сусідніх об'єктах (діагональ не враховується). Додана вартість, що генерується злиттям, дорівнює добутку вартостей двох залучених стартапів. Ви можете вирішити не залучати певний стартап у злиття, у такому випадку додана вартість не генерується. Ваша мета - знайти набір злиттів з максимальною загальною доданою вартістю. Наприклад, значення стартапів, показані на малюнку зліва, можуть бути оптимально злиті, як показано на малюнку справа, для загальної доданої вартості $171$.