注：after_contestケースが追加され、以下に述べる解法はTLEするようになりました。

コインを持たずに移動を開始し、コインが不足したらその時点でどこかから借金してくることにします。

\(\mathrm{dp}[i,j]=\) マス \((i,j)\) から移動する直前の、最小の借金額

というDPをしたくなりますが、これは正しくありません。 なぜなら、(借金額,現在の所持金)が(1,0)よりも(2,100000)の方が良いことがあり得るからです。

そのため、現在の所持金も考慮して

\(\mathrm{dp}[i,j]=\) マス \((i,j)\) から移動する直前の、(借金額,所持金)の一番いい状態

としたくなりますが、「一番いい状態」を決めるのは困難です。そこでさらに

\(\mathrm{dp}[i,j]=\) マス \((i,j)\) から移動する直前の、(借金額,所持金)の一番いい状態としてありえるもの全ての集合

とします。所持金が同じならば借金額は小さい方がよく、借金額が同じならば所持金は大きい方がよいです。このような(借金額,所持金)たちは以下の記事に書かれた方法で高速に操作が可能です。

https://topcoder-g-hatena-ne-jp.jag-icpc.org/skyaozora/20141216.html

集合 \(\mathrm{dp}[i,j]\) の要素数は十分小さいため（←偽）、この問題を高速に解くことができます。

実装例(C++)

実際には「全ての \(i,j\) で集合 \(\mathrm{dp}[i,j]\) の大きさが \(\Theta(ij)\) 程度の大きさとなる」ような入力が存在するため、そのような入力に対するこの解法の計算量は \(\Omega(H^2W^2)\) となりTLEするケースが存在します。