20008. 貨比三家不吃虧

Task Description
「東市買駿馬 西市買鞍韉 南市買轡頭 北市買長鞭」（節錄自《木蘭詩》）

古代人很早就告訴了我們「貨比三家不吃虧」的道理，而當時因為沒有網路的關係，因此木蘭必須親自去採買才可以。
因為手頭有點緊的緣故，木蘭想要用最少的錢買齊這四樣東西且每樣只需要一個，因此木蘭向鄰居打聽了東南西北市中四樣東西的價格以及各條路線的交通費，請你幫木蘭計算各樣物品該去哪裡買才可以使得她的花費最少。

下圖為木蘭的家與東南西北市的位置圖以及各條路線的編號。

木蘭以她的家作為起點，可以任意選擇採買順序與路徑，並且不一定要跑四個市場，同一個市場可以購買任意數量的東西，但請注意每一個市場只能夠去一次（經過沒有買東西也算），而木蘭的家則不限次數，然後最後木蘭必須返回家中。最後花費的金額僅與東西本身的價錢以及交通費用有關。

Input Format
輸入共有以下5行，前四行為東南西北市場中四樣物品各自的價格，最後一行為編號0-7的路線各自所需的費用。
horseE saddleE bridleE whipE
horseS saddleS bridleS whipS
horseW saddleW bridleW whipW
horseN saddleN bridleN whipN
road0 road1 road2 road3 road4 road5 road6 road7
(2000 <= horse <= 5000、500 <= saddle <= 1000、100 <= bridle <= 200、50 <= whip <= 100、10 <= road <= 50)


Output Format
輸出一數值代表木蘭最少花多少錢就可以買齊這四樣東西並回到家裡。


Sample Input

1
2
3
4
5
2500 550 150 80
2800 600 130 75
3000 700 120 70
4000 500 140 90
20 30 25 40 30 20 15 35

Sample Output

1
3285

Sample Input2

1
2
3
4
5
3000 500 180 85
3010 600 150 75
3050 700 170 85
2980 800 165 85
25 40 15 20 20 35 15 30

Sample Output2

1
3805