Вы хотите прорекламировать свой новый бизнес, поэтому собираетесь разместить два плаката на рекламном щите в центре города. Рекламный щит состоит из \(n\) вертикальных панелей шириной \(1\) и различной целочисленной высоты, соединенных горизонтальной перекладиной. \(i\)-я из \(n\) панелей имеет высоту \(h_i\).
Изначально все панели свисают с перекладины (их верхние края лежат на ней), но перед размещением двух постеров разрешается сдвинуть каждую панель вверх на любую целую величину, главное, чтобы она все еще была соединена с перекладиной (нижний край панели лежит под или на ней).
После того, как операции будут сделаны, вы разместите два плаката: один под перекладиной и один над ней. Им не разрешается выходить за перекладину, и они должны полностью располагаться внутри панелей.
Какую максимальную общую площадь могут покрыть два плаката, если вы сделаете оптимальные операции? Заметьте, что вы также можете разместить плакат площади \(0\). Этот случай равносилен размещению одного плаката.
Примечание
В первом тестовом примере мы можем выбрать верхний плакат с площадью \(12\) и нижний плакат с площадью \(6\), как на изображении ниже.
Во втором тестовом примере мы можем покрыть весь рекламный щит, используя один плакат.