|
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Робопёс Тузик, стремительно вращая хвостом, подкатился к торту. Датчики запаха зашкалили, биты в электронном мозгу запрыгали от восторга… N на N кусочков… бисквит, сметанный крем, и главное – орешки! А орешки-то распределены неравномерно, на одних кусках их больше, на других меньше… — Можно! Но только один кусь. Только один… Кусь-манипулятор Тузика был устроен таким образом, что он мог откусить не более 4 кусочков, расположенных в форме буквы Т, с любой стороны, причём строго по границам кусочков. А можно откусить и меньше, если не подходить вплотную или кусать вблизи угла. Не в кусочках счастье, счастье – в орешках! По данным о количестве орешков на каждом куске торта определите, сколько орешков окажутся в Тузике после оптимального куся. Входные данные. В первой строке – натуральное число N, не меньшее 3 и не превосходящее 100. Далее — N строк, в каждой N разделённых пробелами натуральных чисел, количества орешков на кусках торта в очередном ряду. На куске помещается не более 999 орешков. Выходные данные. Натуральное число – максимальное количество орешков, которые может добыть Тузик за один кусь. Для отправки решений необходимо выполнить вход. |