Бале, наместо да учи, фатил да си игра со Excel табелата во неговиот компјутер што се состои од N редици и N колони - N x N полиња, каде полето во i-тата редица и j-тата колона се обележува со (i, j). Притоа, 1 ≤ i, j ≤ N. Во секое поле е сместен по точно еден ненегативен цел број A_ij. Бале може да се движи низ табелата меѓу две соседни полиња со користење на стрелките на тастатурата.

Бале започнува врз полето (1, 1) и со помош на стрелките → и ↓ ќе се движи по едно поле или надесно или надолу се’ додека не стигне врз полето (N, N). Потоа, од полето (N, N), со помош на стрелките ← и ↑ ќе се движи по едно поле или налево или нагоре се’ додека не стигне назад врз полето (1, 1). И на крај, повторно, започнувајќи од полето (1, 1) ќе се движи до полето (N, N), исто така со помош на користење на стрелките → и ↓.

Секој пат кога ќе се најде врз едно поле, Бале ја гледа вредноста во тоа поле и јаде точно толку сончогледови семки колку што е вредноста во тоа поле, а веднаш потоа вредноста во тоа поле ја менува во 0.

За дадена Excel табела пресметајте колку најмногу семки сончоглед може да изеде Бале.

Влез

Во првиот ред даден е бројот N (1 < N ≤ 50) - големината на Excel табелата.
Во следните N редови дадени ви се N ненегативни цели броеви A_ij (0 ≤ A_ij ≤ 1 000 000).

Забелешка:
За 20 поени, за секое поле (i, j) ќе важи A_ij = 1
За други 15 поени, во секоја редица ќе има најмногу три полиња со позитивни вредности.
За други 35 поени, 1 ≤ N ≤ 20

Излез

Во првиот и единствен ред отпечатете го бараниот резултат - најголемиот број на семки што може да ги изеде Бале.

Ограничувања

Временско ограничување: 400 milliseconds
Мемориско ограничување: 64 megabytes

Примери

влез
4
1 2 3 4
1 1 1 1
4 3 2 1
1 1 1 1

излез
27

Објаснување за првиот пример: Бале ќе ги притиска следните стрелки на тастатурата во дадениот редослед: ↓↓↓→→→↑↑↑←←←→↓↓→→↓. На овој начин тој ќе изеде 1 + 1 + 4 + 1 + 1 + 1 + 1 + 1 + 1 + 4 + 3 + 2 + 0 + 0 + 1 + 3 + 2 + 0 + 0 = 27 семки сончоглед.