最適解において、高橋君は通ったマスの中で \(A_{i,j}\) が最大であるマスでのみ現在いるマスに留まる行動を取るとしてよいです（そうでないマスで留まった場合、そのマスに留まらないかわりに通ったマスのうち \(A_{i,j}\) が最大であるマスに留まると解が改善します）。また、このことから一度現在いるマスに留まった場合は、それ以降ずっとそのマスに留まるとしてよいことがわかります。

高橋君がすべての行動を終えた後にいるマスを \((G_i, G_j)\) とおきます。上の事実から、高橋君は \((S_i, S_j)\) から \((G_i, G_j)\) に移動し、\((G_i, G_j)\) に留まることを \(0\) 度以上繰り返すとしてよいです。

\((S_i, S_j)\) から \((G_i, G_j)\) までの移動について考えます。上で示したことから高橋君はこの過程で留まることはありませんが、さらに \(2\) 度以上同じマスにいることがないとしてよいこともわかります。これは \((p,q)\) を \(2\) 度通るとすると、一度 \((p, q)\) を出て \((p, q)\) に戻る過程を取り除き、そのかわりに \((G_i, G_j)\) で留まるとしても解は悪化しないことから従います。

したがって、\((S_i, S_j)\) から \((G_i, G_j)\) への経路は長さが \(HW\) 以下であるもののみ考えればよいです。

これにより素朴な dp で答えが求められることがわかります。

具体的には、\(dp_{i,j,k}\) を \(i\) 回の行動で \((j,k)\) にいるときの楽しさの合計の最大値とすればよいです。答えは \(\max ((K - i) A_{j,k} + dp_{i,j,k})\) となります。

\(i \leq HW\) の範囲のみ計算すればよいため、上の dp は時間計算量 \(O((HW)^2)\) で計算可能です。\(K \leq HW\) のケースなどに注意してください。