駒が辿るルートはループしており, そのループは複数個存在する可能性がある.

まずはループを DFS で検出して \(C_i\) をループごとにルート順に並べる. そして以下の操作をループごとに行う.

次に最初に移動する位置が \(i\), 移動し終わったときの位置が \(j\) のとき (ただし 1 周以上しない) のスコア \(S(i, j)\) を計算する. これは累積和を求めておけば \(O(N^2)\) で計算できる.

ちょうど 1 周したときのスコア \(S_c = \sum C_i\) が正ならば周回を重ねた方が得なので, \(S(i, j)\) に周回を重ねた場合のスコアを加算する. これは

\[T(i, j) = S(i, j) + S_c \floor{ \frac{K-U(i, j)}{L} }\]

と計算できる. ただし, \(L\) はループの長さであり, \(U(i, j)\) は区間の長さで \(j \geq i\) のときは \(j-i+1\), そうでないときは \(j-i+1+L\) となる.

このとき \(\max T(i, j)\) がそのループの最大スコアとなる.