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.
題目大意：
現在有兩個人，分別站在（ax，ay）和（bx，by）處，現在有N個垃圾，需要處理，垃圾箱位于（tx，ty）處，這兩個人每次只能拿一個垃圾，并且拿到垃圾之后必須放到垃圾箱中，對于兩個人來講，每個人的行動都是相對獨立的。問兩個人的路徑和最小是多少，就能夠將所有垃圾都扔到垃圾箱中。
思路：
1、這種思維題還是靠某些典型題的體型所影響。比如51nod 1487 占領資源（topcoder上的題）這道題：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1487
利用到這種極限思維的題還是蠻經典的?？梢砸巹澋揭活惾ド羁逃洃洝?/p>
因為做出來這個題的時候感覺這種極限思維還是蠻有趣的，記憶比較深刻。
2、對于A.B兩個人來講，如果一開始都在垃圾箱處出發，那么ans=2*Σdis（xi，yi）---->（tx，ty）；
對于兩個人A.B，每個人只要都選了一個垃圾去撿，并且都回到了垃圾箱處，那么接下來的路程就相當于一個人來回走。
那么對于暴力思維來講，那就是直接O（n^2）枚舉兩個垃圾，過程維護最小值。顯然這么做是會超時的。
那么接下里從貪心的角度出發，對于ans=2*Σdis（xi，yi）->（tx，ty）-A選擇的第一個垃圾的點到垃圾箱的距離+A選擇的第一個垃圾的點到A初始位子的距離-B選擇的第一個垃圾的點到垃圾箱的距離+B選擇的第一個垃圾的點到A初始位子的距離；
我們肯定是希望后邊這一大長串描述中，A選擇的第一個垃圾的點到A初始位子的距離以及B選擇的第一個垃圾的點到B初始位子的距離的和盡可能的小，然而對于不同的選擇方式，最終答案肯定是不同的。
那么我們不妨設定兩個數組A【】，B【】，一個按照點與A的距離從小到大排序，一個按照與B的距離從小到大排序。
接下來我們可以暴力枚舉兩項，分別作為A選擇的點以及B選擇的點，當然不能忘記，有可能一個人一直不動是正解，這種情況也要枚舉。
3、通過思考和簡單枚舉不難發現對于枚舉的量，其實只要足夠大，就一定不會影響結果。
所以在第一次提交的時候，我A，B數組都枚舉了1000的量，結果是Ac的。（再之后交了一發100的枚舉量，也是Ac的）；
4、這種極限思維還是蠻實用的。
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);    }}