給定一個 N×N 的方形網(wǎng)格，設(shè)其左上角為起點◎，坐標(biāo)為 (1,1) ，X 軸向右為正， Y 軸向下為正，每個方格邊長為 1 ，如圖所示。

一輛汽車從起點◎出發(fā)駛向右下角終點▲，其坐標(biāo)為 (N,N)。

在若干個網(wǎng)格交叉點處，設(shè)置了油庫，可供汽車在行駛途中加油。汽車在行駛過程中應(yīng)遵守如下規(guī)則:

汽車只能沿網(wǎng)格邊行駛，裝滿油后能行駛 K 條網(wǎng)格邊。出發(fā)時汽車已裝滿油，在起點與終點處不設(shè)油庫。

汽車經(jīng)過一條網(wǎng)格邊時，若其 X 坐標(biāo)或 Y 坐標(biāo)減小，則應(yīng)付費用 B ，否則免付費用。

汽車在行駛過程中遇油庫則應(yīng)加滿油并付加油費用 A。

在需要時可在網(wǎng)格點處增設(shè)油庫，并付增設(shè)油庫費用 C (不含加油費用 A )。

N,K,A,B,C 均為正整數(shù)， 且滿足約束: 2≤N≤100,2≤K≤10。

設(shè)計一個算法，求出汽車從起點出發(fā)到達終點的一條所付費用最少的行駛路線。

第一行是 N,K,A,B,C的值。

第二行起是一個N×N 的 0-1 方陣,每行 N 個值,至 N+1 行結(jié)束。

方陣的第 i 行第 j 列處的值為 1 表示在網(wǎng)格交叉點 (i,j) 處設(shè)置了一個油庫,為 0 時表示未設(shè)油庫。各行相鄰兩個數(shù)以空格分隔。

9 3 2 3 6
0 0 0 0 1 0 0 0 0
0 0 0 1 0 1 1 0 0
1 0 1 0 0 0 0 1 0
0 0 0 0 0 1 0 0 1
1 0 0 1 0 0 1 0 0
0 1 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0 1
1 0 0 1 0 0 0 1 0
0 1 0 0 0 0 0 0 0

12

數(shù)據(jù)范圍：

2≤n≤100

2≤k≤10