マス に到達できるかどうかは移動したマス目の合計にのみ依存します。これは、使用した魔法の集合にのみ依存するということなので、大魔法は小魔法を必要なだけ使った後に使うことにして問題ありません。

まずは小魔法のみでの移動を考えます。これは、各マス目から 本の遷移を考えてDPすれば解くことができ、このパートの計算量は です。

先ほどのパートで計算した最短距離配列をそのまま利用して大魔法のナップザックDPを行います。

先ほどのパートではマス目ごとに魔法のイテレーションを回していましたが、今回は大魔法ごとにマス目のイテレーションを回すことで大魔法の使用を高々 回に抑えます。

最短距離配列の後ろから順にDPをしていくことでナップザックDPをインラインに処理することができ、このパートの計算量は です。

したがって全体で計算量は となります。