駅站

各駅站には、最初にちょうど 2 頭の馬がいます。駅站 $i$ の $j$ 番目の馬に乗って移動すると、単位距離当たり $P_{i,j}$ の時間がかかります。したがって、この馬に乗って距離 $D$ を移動すると、$D\times P_{i,j}$ の時間がかかります。

各区間を移動するときは、出発する駅站にいる馬を 1 頭選んで乗ります。乗ってきた馬は到着した駅站に残ります。往路で乗った馬に復路で再び乗ることもできます。

馬を休ませるため、連続する 2 区間で同じ馬に乗ることはできません。この規則の唯一の例外は、駅站 $N$ で折り返す場合です。駅站 $N$ では返事を用意する間に馬も休むため、直前に乗ってきた馬に乗って引き返してもかまいません。

往復にかかる時間は、馬に乗って各区間を移動するのにかかる時間の総和として計算します。最初に各駅站にいる馬の情報が与えられるので、往復にかかる最小時間を求めてください。

続く $N$ 行のうち $i$ 行目に、駅站 $i$ に最初にいる 2 頭の馬の単位距離当たりの所要時間 $P_{i,1}$ と $P_{i,2}$ が空白区切りで与えられます。