| Codeforces Round 131 (Div. 1) |
|---|
| Закончено |
Фурик и Рубик принимают участие в эстафете. Эстафета будет проводиться на большом квадрате, со стороной 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). Рисунок к примеру:
