Фурик и Рубик принимают участие в эстафете. Эстафета будет проводиться на большом квадрате, со стороной 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, 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). Рисунок к примеру:
Путь Фурика отмечен желтым, а Рубика — розовым.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
5
|
5
|
|
2
|
2
11 14
16 12
|
53
|
|
3
|
3
25 16 25
12 18 19
11 13 8
|
136
|