У вас новая, очень интересная работа. Вы — капитан корабля. Ваша задача — провести корабль из одной точки в другую, минимизируя при этом расходы.

Всем известно, что кратчайшее расстояние между любыми двумя точками — отрезок прямой, соединяющий эти точки. Но к сожалению, в море есть остров, поэтому иногда невозможно провести корабль по отрезку прямой между этими точками.

Вы можете двигаться только по безопасным точкам. Точка называется безопасной, если она либо принадлежит прямой, соединяющей начальную и конечную точку, либо находится на границе острова.

Вам повезло — у вас есть умные и сильные рабочие, которые могут помочь в вашем путешествии. Они могут перемещать корабль по морю: это стоит 1 египетский фунт за каждую единицу расстояния по морю. Они так же могут даже нести корабль по суше (они очень сильные!): это стоит 2 египетских фунта за каждую единицу расстояния по территории острова. Ваши деньги рабочие делят между собой поровну, поэтому количество рабочих значения не имеет.

Вы можете перемещать корабль по границе острова, это считается за перемещение по морю.

Вам задана карта моря, вам необходимо определить наименьшую возможную стоимость путешествия.

Вы начинаете в точке (xStart, yStart), и должны приплыть в точку (xEnd, yEnd). Гарантируется, что эти точки различны.

Остров представляет собой выпуклый многоугольник. Никакие 3 точки многоугольника не лежат на одной прямой. Также начальная и конечная точка не лежат внутри или на границе острова. Точки многоугольника заданы в порядке обхода против часовой стрелки.