Дистанционный практикум по программированию

The favourite fairy-tale country of the H&H employees is Berland. Berland consists of N towns. Some of the towns are connected with the portals. All towns are numbered with numbers from 1 to N. The town with number i has portals to M_i closest towns (portals are unidirectional). If two or more towns are on the equal distance then towns with the smaller numbers are chosen. In Berland the distance between two points (x₁, y₁) and (x₂, y₂) is equal to min(|x₁ - x₂|, |y₁ - y₂|) + 1. For each transfer through the portal between two towns due should be paid. The due is equal to the square root of distance between the towns. The amount of due is rounded to the nearest integer using standard rules.

At the face of the war threat some of the towns are united to the United Union (UU). All towns from the UU are called union towns, and other towns are called non-union. To draw the citizens at the union side the following decision was made: the due of transfer from non-union city to the union one is decreased and the due for some other transfers is increased. So if X is a union town and Z is a non-union, the due for the transfer from Z to X is decreased by D_x and for the transfer from X to Z is increased by D_x. If W is also a union town and Y is a non-union, then the due for the transfer from X to W and back is increased by D_x + D_w and the due for the transfer between cities Z and Y is not changed.

Professor Perlov is visiting his grandchild in the town number N. And now he would like to get back to the town number 1. But he is unsure about the optimal route.

Your task is to help the professor to find the cheapest route from town N to town 1. Note, that it is even possible for the professor to earn some money — in this case you should find the route with maximum earning.