原題來自：CEOI 2004

從山頂上到山底下沿著一條直線種植了 n 棵老樹。當(dāng)?shù)氐恼疀Q定把他們砍下來。為了不浪費(fèi)任何一棵木材，樹被砍倒后要運(yùn)送到鋸木廠。

木材只能朝山下運(yùn)。山腳下有一個(gè)鋸木廠。另外兩個(gè)鋸木廠將新修建在山路上。你必須決定在哪里修建這兩個(gè)鋸木廠，使得運(yùn)輸?shù)馁M(fèi)用總和最小。假定運(yùn)輸每公斤木材每米需要一分錢。

你的任務(wù)是編寫一個(gè)程序，讀入樹的個(gè)數(shù)和他們的重量與位置，計(jì)算最小運(yùn)輸費(fèi)用。

輸入的第一行為一個(gè)正整數(shù) n，表示樹的個(gè)數(shù) 。樹從山頂?shù)缴侥_按照 1,2,?,n 標(biāo)號(hào)。

接下來 n 行，每行有兩個(gè)整數(shù) w_i和 d_i 。分別表示第 i 棵樹的重量（公斤為單位）和第 i 棵樹和第 i+1 棵樹之間的距離。最后一個(gè)數(shù) d_n ，表示第 n 棵樹到山腳的鋸木廠的距離。

樣例說明

下圖展示了對(duì)于樣例輸入的最佳伐木場設(shè)置位置，樹木用一個(gè)圓表示，伐木場用黑色標(biāo)出。結(jié)果為：

數(shù)據(jù)范圍與提示:

對(duì)于 97 分的數(shù)據(jù)，2≤n≤2×10⁴,1≤w_i≤10⁴,0≤d_i≤10⁴ ，保證所有樹運(yùn)到山腳的鋸木廠所需要的費(fèi)用小于 2×10⁹分。（本部分?jǐn)?shù)據(jù)為原數(shù)據(jù)）

對(duì)于另外 3 分的數(shù)據(jù)，2≤n≤2×10⁵ ，保證所有計(jì)算均可在 64 位有符號(hào)整數(shù)下進(jìn)行。

信息學(xué)一本通 動(dòng)態(tài)規(guī)劃