題目 PDF 檔在這裡

暈船是什麼可怕的東西 不要暈船

— Ian Wen, 建電一五網管

是的，Ian Wen 不會暈船，他只知道如何讓別人暈船，是個名副其實的大海王。他的休閒日常就是在海灣釣魚，且他作為一個王，想當然他也有一個碩大的皇宮，而皇宮的後院，簡稱後宮，則有 $n$ 個魚塘，裡面養著各種 Ian Wen 釣過的魚，而這些魚如果長時間沒有被 Ian Wen 滋潤到，他們會逐漸喪失活力，更甚者離開魚塘，這是 Ian Wen 最不樂見的。為了避免這種情況發生，他決定在後宮建一些雨水採集器和管道讓他可以持續的滋潤水塘。

對於每一個魚塘，在正上方建立一個雨水採集器的價錢為 $c_i$ ($1 \leq i \leq n$)，而每一個採集器可以接無限多個管道，但每個管道只能從一個魚塘上方出來滋潤該魚塘。若此管道是從位置為 $s$ 的採集器出發，且出口在 $k$，則建立此管道的價格為 $|k - s|$。

Ian Wen 希望自己可以顧到所有 $n$ 個魚塘，所以他決定在每個魚塘上面都建立一個管道，但因為他的金力有限，所以他想知道最少要花多少錢才可以讓每隻魚不喪失活力且不離開他。