Changsha is a well-planned city which is separated into n*n sub-regions by many main roads both from east to west and from south to north. For simplification, we can consider Changsha as a square and in like manner, each sub-region can also be considered as a sub-square. Accordingly, Changsha consists of (n+1)*(n+1) crossroads and 2n*(n+1) undirected roads. Each road connects two adjacent crossroads.
As the mayor of Changsha, QZ has obtained pedestrian flows of each road from two directions. Moreover, each crossroad has an altitude and for citizens, they need to cost their physical power to go uphill(1 unit for 1 unit altitude for each person). Fortunately, going downhill is power-free. Additionally, QZ also knows that the altitude of most northwest crossroad is 0 and that of most southeast crossroad is 1. In addition to that, he knows nothing else and he let you set altitudes of other crossroads to arbitrary values(including minus) to minimize the sum of power costed by all citizens. Could you solve that?
The first line is an integer n, as described
above.
Next is 4n(n+1) lines. Each of them includes
a non-negative integer, representing information of each road’s pedestrian flow
in one direction. The order is: first n(n+1) numbers present all pedestrian
flows from west to east; next n(n+1) numbers are flows from north to south;
subsequent n(n+1) numbers represents flows from east to west; final n(n+1)
numbers are flows from south to north. For each direction, the input is given
from north to south and from west to east when the north-south level is same. (See
sample input)
One number represents the total power costed
by all citizens, rounding to integer.