한 꽃밭에 메뚜기가 살고 있다. 꽃밭은 N행 N열의 정사각형들로 이뤄져 있으며, 각 칸에는 꽃이 하나씩 위치해 있다.

당신은 꽃밭 내의 각 꽃들에 대해 몇 개의 꽃잎을 가지고 있는지를 알고 있다.

메뚜기는 처음 R행 C열의 위치의 꽃에 앉아 있다. 메뚜기는 최대한 많은 꽃들을 방문하고자 한다.

메뚜기는 반드시 다음의 규칙을 지켜야 한다.

1. 메뚜기는 인접한 행 혹은 열로 이동이 가능하다. 인접한 행으로 메뚜기가 점프를 했을 경우 적어도 두 칸 이상 떨어진 열로 이동하여야 하며,

인접한 열로 이동하였을 경우에는 적어도 두 칸 이상 떨어진 행으로 이동해야 한다.

다시 말해서 (r₁ c₁)에서 (r₂ c₂)로 이동할 경우 다음의 조건을 만족해야 한다.

2. 이동하게 되는 다음 꽃의 꽃잎의 수는 현재 꽃의 꽃잎 수 보다 커야 한다.

메뚜기가 방문하게 되는 최대 꽃의 수를 알아내는 프로그램을 작성하라.

권한이 없어요.

메뚜기의 이동 timer 2초 memory 128MB