Anyone Who Disrupts the Festival Needs a Scolding!

Sensei! We have to stop Arata and the Mouryo before they ruin the Shimmoku Festival! Fighting here might set the fireworks alight... so I want to catch Arata with a rope, with help from the Inner Discipline Club.

The plaza is an $N \times N$ grid. I am at the center of the cell in row $1$, column $1$, and Arata is at the center of some cell in the plaza. With the students helping me, we can lay the rope by moving from the center of one cell to the center of another. The Inner Discipline Club students may move only to adjacent cells above, below, to the left, or to the right.

Suppose the Inner Discipline Club students start at row $1$, column $1$, and visit a total of $K+1$ cells $P_0$, $P_1$, $\cdots$, $P_K$ in order.

• $P_0$ is the starting cell, in row $1$, column $1$.
• $P_K$ is the cell containing Arata.

We define the length of the rope as the number of line segments it consists of, namely $K$.

Once we catch Arata with the rope, I have to pull it back in immediately. But the more bends there are, the more the rope catches and resists being pulled, requiring greater force. If it takes too much force, retrieving it will take longer, and Arata might escape or things might become more dangerous in the meantime. So I need to minimize the total force, too.

When the rope currently consists of points $P_0$, $P_1$, $\cdots$, $P_i$, pulling it once does the following.

• The endpoint $P_i$ is removed, leaving only the points $P_0$, $P_1$, , to form the rope.

I must repeat this process to retrieve the entire rope, pulling until only point $P_0$ remains.

We need to catch Arata as quickly as possible, before the Mouryo do anything else. So I will first minimize the length of the rope used to catch her, and among ropes of that minimum length, minimize the total force required to retrieve the entire rope. We need to find how the Inner Discipline Club students should move to minimize these two values. Sensei, will you help me?

Umika appears only in row $1$, column $1$, and there is exactly one cell containing Arata.

It is guaranteed that Arata can be caught.

Time limit

2000 ms

Memory limit

256 MB

Checker

CUSTOM