Робот-лижник

Limits: 2 sec., 256 MiB

Дійшла економічна криза й до карпатських сіл, тепер і там подумують, як її найшвидше відвернути, а задумали зробити це, розвиваючи новий напрям — робототехніку. Але для розвитку, як відомо, необхідні гроші, причому чималі, тому українські ентузіасти наважилися створити першого робота на кошти, якими володіли на той момент, та поїхати до Японії з метою перемоги в конкурсі роботів-лижників та отримати гроші для подальшого розвитку. Найстрашнішим суперником за прогнозами може бути робот японського професора Kazuo Yoshida, який навіть уміє виконувати акробатичні трюки, стрибки та перевороти в повітрі, але навряд це все допоможе йому в здобутті перемоги.

Лижна траса нагадуватиме звичайну слаломну з кількома воротами, через які необхідно буде пройти роботу. Ворота можуть проходитися лише в тому порядку, у якому вони задані на вході, і в жодному разі не можна їх оминати, інакше це каратиметься дискваліфікацією. Уважається, що робот уміє здійснювати різкі повороти без утворення так званих дуг, тобто його траєкторія нагадуватиме звичайнісіньку ламану, яка відповідно перетинатиме відрізки, утворені воротами, крім того, траса побудована таким чином, що частини ламаної до та після перетину, в околі її перетину з воротами лежатимуть у різних півплощинах відносно воріт.

Input

У першому рядку задано ціле число \(n\) — кількість воріт на трасі.

У наступних \(n\) рядках задано по чотири цілих числа — дві пари координат \(x\), \(y\) кінців воріт.

У наступних двох рядках задано координати початку \(s_x\), \(s_y\) та кінця \(f_x\), \(f_y\) траси, куди робот має потрапити після проходу всіх воріт.

Output

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

Constraints

\(1 \le n \le 4\),

\(|x|, |y|, |s_x|, |s_y|, |f_x|, |f_y| \le 10^3\),

ворота не вироджуватимуться в точку,

ніяка пара воріт не перетинатиметься.

Samples

Input (stdin) сopy	Output (stdout) сopy
2 4 3 9 3 -8 8 -13 8 0 0 0 23	35.000