It was recycling day in Kekoland. To celebrate it Adil and Bera went to Central Perk where they can take bottles from the ground and put them into a recycling bin.

We can think Central Perk as coordinate plane. There are n bottles on the ground, the i-th bottle is located at position(x_i,?y_i). Both Adil and Bera can carry only one bottle at once each.

For both Adil and Bera the PRocess looks as follows:

Adil and Bera may move independently. They are allowed to pick bottles simultaneously, all bottles may be picked by any of the two, it's allowed that one of them stays still while the other one continues to pick bottles.

They want to organize the process such that the total distance they walk (the sum of distance walked by Adil and distance walked by Bera) is minimum possible. Of course, at the end all bottles should lie in the recycling bin.

First line of the input contains six integers a_x,a_y,b_x,b_y,t_x andt_y (0?≤?a_x,?a_y,?b_x,?b_y,?t_x,?t_y?≤?10⁹) — initial positions of Adil, Bera and recycling bin respectively.

The second line contains a single integer n (1?≤?n?≤?100?000) — the number of bottles on the ground.

Then follow n lines, each of them contains two integersx_i andy_i (0?≤?x_i,?y_i?≤?10⁹) — position of the i-th bottle.

It's guaranteed that positions of Adil, Bera, recycling bin and all bottles are distinct.

Print one real number — the minimum possible total distance Adil and Bera need to walk in order to put all bottles into recycling bin. Your answer will be considered correct if its absolute or relative error does not exceed10^?-?6.

Namely: let's assume that your answer is a, and the answer of the jury isb. The checker program will consider your answer correct if.

3 1 1 2 0 031 12 12 3Output
11.084259940083Input
5 0 4 2 2 055 23 05 53 53 3Output
33.121375178000Note
Consider the first sample.
Adil will use the following path: .
Bera will use the following path: .
Adil's path will be  units long, while Bera's path will be units long.
題目大意：
現(xiàn)在有兩個(gè)人，分別站在（ax，ay）和（bx，by）處，現(xiàn)在有N個(gè)垃圾，需要處理，垃圾箱位于（tx，ty）處，這兩個(gè)人每次只能拿一個(gè)垃圾，并且拿到垃圾之后必須放到垃圾箱中，對(duì)于兩個(gè)人來講，每個(gè)人的行動(dòng)都是相對(duì)獨(dú)立的。問兩個(gè)人的路徑和最小是多少，就能夠?qū)⑺欣既拥嚼渲小?/p>
思路：
1、這種思維題還是靠某些典型題的體型所影響。比如51nod 1487 占領(lǐng)資源（topcoder上的題）這道題：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1487
利用到這種極限思維的題還是蠻經(jīng)典的。可以規(guī)劃到一類去深刻記憶。
因?yàn)樽龀鰜磉@個(gè)題的時(shí)候感覺這種極限思維還是蠻有趣的，記憶比較深刻。
2、對(duì)于A.B兩個(gè)人來講，如果一開始都在垃圾箱處出發(fā)，那么ans=2*Σdis（xi，yi）---->（tx，ty）；
對(duì)于兩個(gè)人A.B，每個(gè)人只要都選了一個(gè)垃圾去撿，并且都回到了垃圾箱處，那么接下來的路程就相當(dāng)于一個(gè)人來回走。
那么對(duì)于暴力思維來講，那就是直接O（n^2）枚舉兩個(gè)垃圾，過程維護(hù)最小值。顯然這么做是會(huì)超時(shí)的。
那么接下里從貪心的角度出發(fā)，對(duì)于ans=2*Σdis（xi，yi）->（tx，ty）-A選擇的第一個(gè)垃圾的點(diǎn)到垃圾箱的距離+A選擇的第一個(gè)垃圾的點(diǎn)到A初始位子的距離-B選擇的第一個(gè)垃圾的點(diǎn)到垃圾箱的距離+B選擇的第一個(gè)垃圾的點(diǎn)到A初始位子的距離；
我們肯定是希望后邊這一大長串描述中，A選擇的第一個(gè)垃圾的點(diǎn)到A初始位子的距離以及B選擇的第一個(gè)垃圾的點(diǎn)到B初始位子的距離的和盡可能的小，然而對(duì)于不同的選擇方式，最終答案肯定是不同的。
那么我們不妨設(shè)定兩個(gè)數(shù)組A【】，B【】，一個(gè)按照點(diǎn)與A的距離從小到大排序，一個(gè)按照與B的距離從小到大排序。
接下來我們可以暴力枚舉兩項(xiàng)，分別作為A選擇的點(diǎn)以及B選擇的點(diǎn)，當(dāng)然不能忘記，有可能一個(gè)人一直不動(dòng)是正解，這種情況也要枚舉。
3、通過思考和簡單枚舉不難發(fā)現(xiàn)對(duì)于枚舉的量，其實(shí)只要足夠大，就一定不會(huì)影響結(jié)果。
所以在第一次提交的時(shí)候，我A，B數(shù)組都枚舉了1000的量，結(jié)果是Ac的。（再之后交了一發(fā)100的枚舉量，也是Ac的）；
4、這種極限思維還是蠻實(shí)用的。
Ac代碼：
#include<stdio.h>#include<string.h>#include<math.h>#include<iostream>#include<algorithm>using namespace std;#define ll __int64struct node{    ll x,y;    double dis0;    double disa;    double disb;    int pos;}a[100060],b[100060];double dis(ll a,ll b,ll c,ll d){    return sqrt((a-c)*(a-c)+(b-d)*(b-d));}int cmp(node a,node b){    if(a.disa!=b.disa)    return a.disa<b.disa;    else return a.disb<b.disb;}int cmp2(node a,node b){    if(a.disb!=b.disb)    return a.disb<b.disb;    else return a.disa<b.disa;}int main(){    ll ax,ay,bx,by,tx,ty;    while(~scanf("%I64d%I64d%I64d%I64d%I64d%I64d",&ax,&ay,&bx,&by,&tx,&ty))    {        ll n;        scanf("%I64d",&n);        double minna=-1,minna0;        double minnb=-1,minnb0;        double sum=0;        for(int i=0;i<n;i++)        {            scanf("%I64d%I64d",&a[i].x,&a[i].y);            a[i].pos=i;            b[i].pos=i;            a[i].dis0=dis(a[i].x,a[i].y,tx,ty);            a[i].disa=dis(a[i].x,a[i].y,ax,ay);            a[i].disb=dis(a[i].x,a[i].y,bx,by);            sum+=2*a[i].dis0;            b[i].dis0=a[i].dis0,b[i].disa=a[i].disa;b[i].disb=a[i].disb;        }        double ans=2000000000000000000;        sort(a,a+n,cmp);        sort(b,b+n,cmp2);        for(int i=0;i<n&&i<100;i++)        {            for(int j=0;j<n&&j<100;j++)            {                if(a[i].pos==b[j].pos)                {                    ans=min(ans,min(sum-a[i].dis0+a[i].disa,sum-b[j].dis0+b[j].disb));                    continue;                }                ans=min(ans,sum-a[i].dis0-b[j].dis0+a[i].disa+b[j].disb);            }        }        printf("%.12lf/n",ans);    }}