C. Эстафета
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Фурик и Рубик принимают участие в эстафете. Эстафета будет проводиться на большом квадрате, со стороной n метров. Данный квадрат разбит на n × n клеточек (представляют собой квадраты со стороной 1), в каждой такой клеточке стоит некоторое число.

Вначале эстафеты Фурик стоит в клеточке с координатами (1, 1), а Рубик в клеточке с координатами (n, n). Сразу после старта Фурик бежит к Рубику, при этом, если Фурик стоит в клеточке с координатами (i, j), то он может перейти в клеточку с координатами (i + 1, j) или (i, j + 1). После того, как Фурик прибежит к Рубику, Рубик побежит из клеточки с координатами (n, n) в клеточку с координатами (1, 1), при этом, если Рубик стоит в клеточке с координатами (i, j), то он может перейти в клеточку с координатами (i - 1, j) или (i, j - 1). Ни Фурик, ни Рубик не имеют права выходить за пределы поля, иначе они будут дисквалифицированы.

Чтобы выиграть эстафету Фурику и Рубику нужно набрать как можно больше очков. Количество очков — это сумма чисел в клеточках, по которым прошлись Фурик и Рубик, каждая клеточка учитывается в сумме только один раз.

Посчитайте максимальное количество очков, которое могут заработать Фурик и Рубик на эстафете.

Входные данные

В первой строке находится единственное целое число (1 ≤ n ≤ 300). В следующих n строках находятся по n целых чисел: j-ое число в i-ой строке ai, j ( - 1000 ≤ ai, j ≤ 1000) — число, записанное в клеточке с координатами (i, j).

Выходные данные

В единственную строку выведите одно число — ответ на задачу.

Примеры
Входные данные
1
5
Выходные данные
5
Входные данные
2
11 14
16 12
Выходные данные
53
Входные данные
3
25 16 25
12 18 19
11 13 8
Выходные данные
136
Примечание

Пояснение ко второму примеру. Фурику выгодно пройти по маршруту: (1, 1), (1, 2), (2, 2), а Рубику: (2, 2), (2, 1), (1, 1).

Пояснение к третьему примеру. Оптимальный маршрут Фурика: (1, 1), (1, 2), (1, 3), (2, 3), (3, 3), а Рубика: (3, 3), (3, 2), (2, 2), (2, 1), (1, 1). Рисунок к примеру:

Путь Фурика отмечен желтым, а Рубика — розовым.