Каждый настоящий Царь в своей жизни должен поработить мир, провести финал чемпионата мира Codeforces, выиграть розовую панду в тире и объехать свое царство.

Первые три вещи Царь Цопа уже сделал в своей жизни. Осталось всего лишь объехать свое Царство. Оно, по неизвестным науке причинам, представляет собой бесконечную декартову систему координат, на которой отмечены города. Каждый город будем считать точкой на этой плоскости. Буквально перед самым отъездом, к Царю пришел гонец и сообщил пренеприятнейшее известие о том, что на самом деле города в Царстве расположены в точках с координатами (x₁, 0), (x₂, 0), ..., (x_n, 0), а еще один город в точке (x_n + 1, y_n + 1) (то есть всего их в Царстве ровно n + 1).

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

Никакие два города не могут находиться в одной точке.