给定一个N*N 的方形网格，设其左上角为起点◎，坐标为（1，1），X轴向右为正，Y轴向下为正，每个方格边长为1。一辆汽车从起点◎出发驶向右下角终点▲，其坐标为（N，N）。在若干个网格交叉点处，设置了油库，可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下规则：

（1）汽车只能沿网格边行驶，装满油后能行驶K 条网格边。出发时汽车已装满油，在起点与终点处不设油库。

（2）当汽车行驶经过一条网格边时，若其X 坐标或Y 坐标减小，则应付费用B，否则免付费用。

（3）汽车在行驶过程中遇油库则应加满油并付加油费用A。

（4）在需要时可在网格点处增设油库，并付增设油库费用C（不含加油费用A）。

（5）(1)～(4)中的各数N、K、A、B、C均为正整数。



编程任务：

求汽车从起点出发到达终点的一条所付费用最少的行驶路线。



数据输入：

第一行是N，K，A，B，C的值，2 <=N<=100，2<=K<=10。



第二行起是一个N*N 的0-1方阵，每行N 个值，至N+1行结束。方阵的第i

行第j 列处的值为1 表示在网格交叉点（i，j）处设置了一个油库，为0 时表示未设油库。各行相邻的2 个数以空格分隔。



结果输出:

第1 行中的数是最小费用值。-Given an N* N square grid, set the upper left corner as a starting point ◎, coordinates (1,1), X-axis to the right is positive, Y axis is under, each square of side length 1. A car starting from the starting point towards lower right corner of the end ◎ ▲, the coordinates (N, N). In the number of grid intersection points, set up oil depot, car driving on the way for refueling. Car in motion the process should comply with the following rules:

(1) car can only travel along the grid edge, full of oil can travel the grid section K edge. When the car was filled with oil starting in the beginning and the end of office does not set oil tanks.

(2) when the vehicle traveling through a grid edge, if the X coordinate or Y coordinate decreases, then meet the cost of B, or to avoid payment.

(3) car encountered in the process of moving fuel tank should fill up and pay costs of A.

(4) require the grid point when additional fuel tank, and pay the additional cost of tank C (excluding fuel costs