今日は1年に一回のお祭りの日です。ポリアンナちゃんは屋台を引っ張る役割を担っています。

お祭りは縦 $H$ $\times$ 横 $W$ マスからなる町で開催されます。
ポリアンナちゃんはスタート地点 $ T_{(1, 1)} $ からゴール地点 $ T_{(H, W)} $ へ向かって屋台を引っ張ります。このとき、ポリアンナちゃんは右か下にしか屋台を引っ張ることができません。

お祭りの日はあいにくの雨上がりであったため、路面が荒れているマスとそうでないマスが町の中にあります。1マス移動するとき、移動先のマスが $T_{(i, j)} = 0$ であれば平坦な路面であるためコストはかかりません。しかし、$ T_{(i, j)} = 1$ であれば、路面が荒れているため移動コストが $C$ かかります。

ポリアンナちゃんはなるべくコストがかからないようにしてゴール地点まで屋台を引っ張りたいです。スタート地点からゴール地点まで屋台を引くときにかかるコストの総和の最小値を求めてください。

• $ 2 \leq H, W \leq 10^3 $
• $ 0 \leq C \leq 10^3 $
• $ T_{(i, j)} = 0 \ or \ 1$
• $ T_{(1, 1)} = 0 $

$ H \ W \ C $
$ T_{(1, 1)} T_{(1, 2)} \dots T_{(1, W)}$
$ \vdots $
$ T_{(H, 1)} T_{(H, 2)} \dots T_{(H, W)}$

答えを出力してください。