ИЮ2020: Линейные алгоритмы (Н2)

Подводная лодка легла на грунт на мелководье. Для её обнаружения используются данные спутника, который с высокой точностью измеряет отклонение высоты поверхности воды от среднего уровня моря. Снимок, получаемый со спутника, представляет собой массив из \(h\) строк по w элементов в каждой строке.

Введём на снимке систему координат с осью абсцисс, направленной вдоль строк снимка слева направо, и осью ординат, направленной вдоль столбцов снимка снизу вверх. Потенциальное изображение подводной лодки представляет собой любое множество элементов массива, состоящее из следующих частей:

• «корпус» — полоса из элементов с координатами от \((x_1, y_1)\) до \((x_2, y_1)\), где \(x_1 \lt x_2\);

• «рубка» — полоса из элементов с координатами от \((x_3, y_1)\) до \((x_3, y_2)\), где \(x_1 \le x_3 \lt x_2; y_1 \le y_2\);

• «хвост» — полоса из элементов с координатами от \((x_4, y_3)\) до \((x_4, y_4)\), где \(x_3 \lt x_4 \le x_2; y_3 \le y_1 \le y_4\). Поскольку подводная лодка находится вблизи поверхности в районе с сильным течением, уровень воды над ней немного повышается. Поэтому изображением подводной лодки на снимке будем считать потенциальное изображение с максимально возможной суммой входящих в него элементов массива.

Требуется написать программу, которая находит на снимке изображение подводной лодки и выводит сумму его элементов.