\(a_i\) 円払うと宝箱 \(i\) の解錠を行う \(N\) 人の鍵屋がいることにします。 このような鍵屋を追加すると、答えを変えることなく、最適解に全ての宝箱を解錠したものが必ず存在することが保証できます。

そのような最適解を求めることを考えます。全ての宝箱を解錠することから \(X= \sum_{i=1}^{N}a_i\) です。つまり、全ての宝箱を解錠する際に鍵屋に支払う金額の最小化のみを考えればよいです。

頂点 \(0,1,\ldots,N\) を用意します。 宝箱 \(l,l+1,\ldots,r\) を \(c\) 円で解錠するような鍵屋が存在したなら頂点 \(l-1\)から 頂点 \(r\) に向かう重み \(c\) の有向辺を張ります。 また、頂点 \(i\) から頂点 \(i-1\) へ向かう重み \(0\) の有向辺を張ります。

このグラフにおける頂点 \(0\) から \(N\) への最短路の長さが全ての宝箱を解錠する際に鍵屋に支払う金額としてありうる値の最小値です。 ダイクストラ法により \(O((N+M) \log (N+M))\) で求めることができ十分高速です。