すべてのガチャとコインを通らなければなりません。またある地点について、座標 \(0\) からその地点までの（コインの枚数）\(-\)（ガチャの個数）が負の場合には、上の値が \(0\) 以上になる地点まで行ったあとまた戻ってくる必要があります。

ガチャまたはコインのある地点ごとに座標を区切って隣り合う地点同士の間を区間と呼びます。（コインの枚数）\(-\)（ガチャの個数）が負の区間については1.そこを通り過ぎて、2. また戻ってきて、3. その後また座標が正の方向に進む、ため区間の長さの \(3\) 倍の移動距離が必要です。ただし1. のときに最も大きい座標まで到達していたなら 3. を省略することができるため区間の長さの \(2\) 倍になります。

上のことから最適な行動はある最終地点 \(f\) があり、\(f\)より以前では負の区間は \(3\) 回、正の区間は \(1\) 回通る。\(f\) 以降では最後まで到達したあと \(f\) まで戻ってくるため、負の区間は \(2\) 回、正の区間も \(2\) 回通るという構造になります。

よって最終地点 \(f\) を全ての地点について全探索すればよいです。累積和を用いると最終地点を決め打ったときの移動距離を \(O(1)\) で求めることができるので、全体で \(O(N)\) で解くことができました。