cho.sh

Milk City

On an N by N grid of milk shops, walk from the top-left to the bottom-right cell moving only right or down, buying packs along the way so the drink types cycle 0,1,2,0,..., and maximize the number of packs bought.

Medium7Dynamic programmingMatrixNo attempts yetTime limit1sMemory limit256 MB

Problem

Yeonghak likes strawberry milk, chocolate milk, and banana milk. He is a picky drinker, so he fixed the order in which he drinks them.

  1. The first pack he drinks is strawberry milk.
  2. After a pack of strawberry milk he drinks one pack of chocolate milk.
  3. After a pack of chocolate milk he drinks one pack of banana milk.
  4. After a pack of banana milk he drinks one pack of strawberry milk again.

On his milk trip Yeonghak reached a city full of milk shops. The city is a square grid with side NN, and every cell holds one shop. Each shop sells only one of the three kinds.

Yeonghak starts at the northwest cell (1,1)(1, 1) and walks to the southeast cell (N,N)(N, N). Every move takes him one cell east or one cell south, so he never returns to a shop he has already passed. At each cell on his route he either buys and drinks one pack from that shop or walks past it. The order rule above always holds, and he never drinks two packs in one cell. He may drink at the starting cell and at the final cell.

Find the largest number of packs Yeonghak can drink.

Input

The first line has the side length NN of the city. (1≤N≤10001 \le N \le 1000)

Each of the next NN lines describes one row of the city and has NN integers separated by spaces. 0 is a shop that sells strawberry milk, 1 is a shop that sells chocolate milk, and 2 is a shop that sells banana milk. No integer other than 0, 1, and 2 is given.

Output

Print the largest number of packs Yeonghak can drink.