最短路

题号：NC234577
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

题目背景

嘤嘤最近在摸鱼。她每天原神只上线20分钟，做一下每日、清一下体力就下号了。（你看，她题面都写的那么简洁，这摸鱼，多是一件美事啊！）

她在摸鱼，所以她渊下宫还没有开始肝，有很多的宝箱、常世之荚、渊海矿髓、珊瑚蝶等物资，她必须全部拿完！

她在摸鱼，所以她想找到一条最短路径将这些物资收集完全！

她在摸鱼，所以这个任务就交给你了！

PS: 爱摸鱼的嘤嘤同学拿着从渊下宫收集的原石在0人池歪了77，嘤嘤气的说起了嘤语：嘤！嘤嘤嘤！嘤嘤嘤嘤嘤嘤！嘤嘤嘤！！嘤嘤嘤！！嘤嘤嘤嘤嘤！

题目描述

首先，我们忽略高度，将渊下宫看成二维地图，嘤嘤的初始位置为 $(0,0)$ 。

嘤嘤知道地图上所有宝箱、常世之荚、渊海矿髓、珊瑚蝶、传送锚点的位置，她可以在初始位置或到达一个宝箱、常世之荚、渊海矿髓或珊瑚蝶的位置时在此位置建立一个口袋锚点。

传送锚点和口袋锚点的作用是：你可以在任意位置传送至任意锚点。（注意：口袋锚点可以同时存在多个，此处与游戏设定不同）

你需要帮助嘤嘤计算出她找完所有物资所需的最短路径。

在第一行中，先输入四个整数 $a,b,c,d(0 \le a,b,c,d \le 500)$ ,表示宝箱、常世之荚、渊海矿髓、珊瑚蝶的个数，再输入一个整数 $n(0 \le n \le 1000)$ 表示传送锚点的位置。

接下来 $a$ 行，每行两个整数 $x,y(0 \le x,y \le 10^9)$ ，表示宝箱的位置。

接下来 $b$ 行，每行两个整数 $x,y(0 \le x,y \le 10^9)$ ，表示常世之荚的位置。

接下来 $c$ 行，每行两个整数 $x,y(0 \le x,y \le 10^9)$ ，表示渊海矿髓的位置。

接下来 $d$ 行，每行两个整数 $x,y(0 \le x,y \le 10^9)$ ，表示珊瑚蝶的位置。

接下来 $n$ 行，每行两个整数 $x,y(0 \le x,y \le 10^9)$ ，表示传送锚点的位置。

数据保证一个位置最多只有一个宝箱、常世之荚、渊海矿髓或珊瑚蝶。

一个实数，表示嘤嘤从初始位置 开始收集完所有物资的最短路径经过的距离。

你的答案与正确答案误差的绝对值不应超过  。

示例1

复制

复制

3.0000000000

你可以从初始位置(0,0)传送至传送锚点(1,0)，然后从(1,0)移动1到达宝箱(2,0)，并在(2,0)建立一个口袋锚点，再从(2,0)移动1到达常世之荚(3,0)，从(3,0)传送回口袋锚点(2,0)，从(2,0)移动1到达渊海矿髓(2,1)，所以最短路径为3