ABC188 E - Peddler (500)
$ X \lt Yという条件があるので、町を小さい順に見ていく
それぞれの町で以下を行う
その町に到達できる中で最安の金の価格を求める
それぞれの町でこの値を記録しておけば全体$ O(M)でできる
そのような町が無い場合は適当な非常に大きい値にしておく
この町で金を売ったことにして購入価格との差分が現在の答えより大きかったらそれを更新する
その町に到達できる中で最安の金の価格よりこの町の価格が安かったら最安値を更新する
内側のループが全体で$ O(M)回回るので$ O(M)