В Бургас има N автобусни спирки, номерирани с числата от 1 до N, между които се движат автобуси. Автобусната компания е публикувала разстоянията между всеки 2 съседни спирки, както и цената P на километър. Помогнете на учениците да изчислят най-ниската цена на пътуването между всеки 2 спирки в града.

Вход:
На първи ред от стандартният вход е даден броят N на спирките. Следват NxN числа (N реда и N стълба), които задават разстоянията между всеки 2 съседни спирки. Ако спирките не са съседни, на съответното място стои -1. На следващия ред са дадени 2 числа, които задават номерата на началната и крайната спирка. На последния ред от стандартния вход е дадено числото, което задава цената P на километър.

Изход:
На стандартния изход изведете най-ниската цена на пътуване между избраните спирки.

Органичения:
2 ≤ N ≤ 100

Примерен вход:	
4
0 0.5 0.2 -1
0.5 0 -1 0.3 
0.2 -1 0 0.4
-1 0.3 0.4 0
1 4
0.5	

Примерен изход:
0.30

Пояснение към примера: 
минималният път е 0.2 + 0.4 = 0.6 км; 0.6 х 0.5 (цена) = 0,30 лв.