Помогите с решением пожалуйста

Arthur Karapetyan

Город Длинноград протянулся вдоль реки Длинной на L километров. Построенный в лучших градостороительных традициях конца 60-х годов XX века, город разбит на квадратные кварталы размером 1 * 1 километр, его ширина составляет 3 километра. Федеральная сеть продуктовых магазинов у дома "Вектор" провела исследование с использованием машинного обучения и определила потенциальную прибыль от покупателей в каждом квартале. Прибыль могла оказаться как положительной, так и отрицательной (в случае, если операционные расходы не будут покрываться доходами). Магазины можно строить только на внутренних перекрестках дорог. Каждый магазин охватывает 4 соседних с ним квартала (квадрат 2 на 2 квартала). По опыту работу в других городах выяснилось, что если один квартал охватывается сразу двумя магазинами сети, то жители начинают нервничать и жалуются в федеральную антимонопольную службу, поэтому строго запрещено строить магазины так, чтобы один и тот же квартал охватывался двумся разными магазинами. Определите, какую максимальную прибыль может получить федеральная сеть магазинов в Длиннограде. Количество магазинов может быть любым (в том числе нулевым, если строить магазины в Длиннограде не выгодно). Формат входных данных В первой строке задается число L (2 ≤ L ≤ 100000) - длина города Длиннограда. В следующих трёх строках (каждая содержит по L чисел) записана прибыль от кварталов (целые числа, по модулю не превосходящие 2 * 109). Формат результата Выведите максимальную суммарную прибыль от строительства магазинов.

1 чел.