最短路
题号: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 行,每行两个整数  ,表示珊瑚蝶的位置。

接下来 n 行,每行两个整数  ,表示传送锚点的位置。

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

输出描述:

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

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

输入

复制
1 1 1 0 1
2 0
3 0
2 1
1 0

输出

复制
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