Археологи

Ваша команда мисливців за скарбами щойно виявила величезний археологічний пам'ятник, наповнений дорогоцінними металами та цінними старовинними предметами. Пам'ятник складається з $n$ місць для розкопок, розташованих в одну лінію.

Початковий план передбачає, що кожне з $n$ місць розкопок приноситиме чистий прибуток. Прибуток, пов'язаний з $i$-м місцем, дорівнює p_i. Це означає, що ваша команда отримуватиме p_i доларів за кожен метр, викопаний на $i$-му місці. Зверніть увагу, що p_i може бути від'ємним, що вказує на те, що витрати на експлуатацію екскаваторної техніки перевищують фактичну вигоду від копання на $i$-му місці.

Звісно, ви захочете викопати якомога більше в найбільш прибуткових місцях. Однак, щоб уникнути зсувів, не можна створювати занадто круті схили. Точніше, для будь-яких двох сусідніх точок різниця між глибиною копання на цих точках не може перевищувати $1$ метр. Зокрема, місця $1$ і $n$ можна викопати на глибину не більше $1$ метра.

Який максимальний чистий прибуток ви зможете отримати за цих умов?

Наприклад, нижче наведено приклад плану розкопок, який є оптимальним для першого прикладу. Чистий прибуток такого плану дорівнює $8$.