Problem: The Kingdom of Neva is home to two ethnic groups, the Totata and the Tutete. The biggest feature of the Totata tribe is that they eat sweet and sour pork with pineapple. However, the Tutete tribe eats vinegared pork in pineapple. These two peoples couldn't get along with each other, and the Totata and Tutete have been in conflict for hundreds of years.

One day, a petition arrived from two ethnic groups under King Neva. According to it, the Totata tribe wants to build a road connecting the town A and the town B where they live. On the other hand, the Tutete tribe also wants to build a road connecting the town C and the town D where they live.

To prevent the two races from clashing, the roads of the Totata and Tutete cannot be crossed. Also, due to technical restrictions, it is only possible to build a road that connects the two cities in a straight line. In other words, if necessary, instead of connecting city A and city B directly with a road, it would indirectly connect city A and city B via some Totata towns (of course, of the Tutete tribe). Do not go through the city). At that time, the roads connecting the towns of the Totata tribe may intersect. The same applies to town C and town D.

Building a road costs proportional to its length. Therefore, I would like to make the total length of the roads to be constructed as short as possible while satisfying the conditions. Now, what is the minimum length?



Input

NA NB
xA, 1 yA, 1
xA, 2 yA, 2
..
..
..
xA, NA yA, NA
xB, 1 yB, 1
xB, 2 yB, 2
..
..
..
xB, NB yB, NB


The integer NA (2 ≤ NA ≤ 1,000) and the integer NB (2 ≤ NB ≤ 1,000) are written on the first line of the input, separated by blanks. This means that there are NA towns where the Totata tribe lives and NB towns where the Tutete tribe lives in the Kingdom of Neva. In the initial state, no road has been built anywhere.

The following NA line contains the integers xA, i (-10,000 ≤ xA, i ≤ 10,000) and the integers yA, i (-10,000 ≤ yA, i ≤ 10,000), separated by blanks. The geography of the Kingdom of Neva is represented by a two-dimensional Cartesian coordinate plane, and the integers xA, i and yA, i written on the 1 + i line are the position coordinates of the i-th city where the Totata tribe lives (xA, i, yA). , I). (xA, 1, yA, 1) and (xA, 2, yA, 2) are the coordinates of the two cities to be connected.

On the following NB line, the integers xB, i (-10,000 ≤ xB, i ≤ 10,000) and the integers yB, i (-10,000 ≤ yB, i ≤ 10,000) are written separated by blanks. The integers xB, i and yB, i written on the 1 + NA + i line indicate that the position coordinates of the i-th city where the Ytterbium live are (xB, i, yB, i). (xB, 1, yB, 1) and (xB, 2, yB, 2) are the coordinates of the two cities to be connected.

It can be assumed that the coordinates of the two cities are different and that none of the three cities are on the same straight line.

Output

When the road is constructed so as to meet the conditions of the problem statement, output the minimum value of the total length of the road. The "length" here is the Euclidean distance. However, if you cannot build a road that meets the conditions, output -1 instead. The output may contain errors, but the relative error to the true value must be less than 10-9.

Examples

Input

2 2
0 0
1 1
2 0
2 -1


Output

2.414213562373


Input

2 3
4 0
0 0
2 3
2 -2
3 1


Output

-1


Input

5 2
-2 1
1 2
-1 3
-1 5
1 4
0 4
0 0


Output

12.359173603117

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
#define fi first
#define se second
#define show(x) cerr<<#x<<"="<<x<<"\n"
typedef long long ll;
using namespace std;
//const ll MOD=(ll)1e9+7;
const double inf=1e9;
const int dy[]={1,0,-1};
const int dx[]={1,0,-1};

//END CUT HERE
//幾何ライブラリ
//ほぼ、https://ei1333.github.io/algorithm/geometry_new.html からパクりました
//
//
using Real=double;//問題によってはlong double に変更してください
const Real EPS=1e-8;//問題によって値を変更してください
const Real PI=acos(-1.0);//3.141592653589793238...
inline bool eq(Real a,Real b){return fabs(b-a)<EPS;}//誤差を考慮した等価判定
static const int COUNTER_CLOCKWISE=1;
static const int CLOCKWISE=-1;
static const int ONLINE_BACK=2;
static const int ONLINE_FRONT=-2;
static const int ON_SEGMENT=0;
typedef complex<Real> Point;//点

//直線
struct Line{
    Point p1,p2;
    Line()= default;
    Line(Point a,Point b):p1(a),p2(b){};
};

//線分
struct Segment:Line{
    Segment()= default;
    Segment(Point a,Point b):Line(a,b){}
};

//円
/*class circle{
    Point a;
    Real r;
    //Circle()= default;
    circle(Point a,Real r):a(a),r(r){};
};*/

typedef Point Vector;//ベクトル
typedef vector<Point> Polygon;//多角形
typedef vector<Line> Lines;
typedef vector<Segment> Segments;
typedef vector<Point> Points;

Point rotate(Real theta,const Point& p){
    return Point(cos(theta)*p.real()-sin(theta)*p.imag(),sin(theta)*p.real()+cos(theta)*p.imag());
}

Real radian_to_degree(Real r){
    return (r*180.0/PI);
}

Real degree_to_radian(Real d){
    return (d*PI/180.0);
}

Point operator*(const Point &p, const Real &d) {
  return Point(real(p) * d, imag(p) * d);
}

Real get_angle(const Point& a,const Point& b,const Point& c){
    const Point v(b-a),w(c-b);
    Real alpha=atan2(v.imag(),v.real()),beta=atan2(w.imag(),w.real());
    if(alpha>beta)swap(alpha,beta);
    Real theta=beta-alpha;
    return min(theta,2*PI-theta);
}

//点同士の大小比較
namespace std {
    bool operator<(const Point &a, const Point &b) {
        return a.real() != b.real() ? a.real() < b.real() : a.imag() < b.imag();
    }
}

//外積
Real cross(const Point& a,const Point& b){
    return a.real()*b.imag()-a.imag()*b.real();
}

//内積
Real dot(const Point& a,const Point& b){
    return a.real()*b.real()+a.imag()*b.imag();
}


int ccw(Point a,Point b,Point c){
    b=b-a;c=c-a;
    if(cross(b,c)>EPS)return COUNTER_CLOCKWISE;//1
    if(cross(b,c)<-EPS)return CLOCKWISE;//-1
    if(dot(b,c)<0)return ONLINE_BACK;//2
    if(norm(b)<norm(c))return ONLINE_FRONT;//-2
    return ON_SEGMENT;//0
}

//直交判定
bool isOrthogonal(Vector a,Vector b){
    return eq(dot(a,b),0.0);
}

bool isOrthogonal(Point a1,Point a2,Point b1,Point b2){
    return eq(dot(a1-a2,b1-b2),0.0);
}

bool isOrthogonal(Segment a,Segment b){
    return eq(dot(a.p1-a.p2,b.p1-b.p2),0.0);
}

//平行判定
bool isParallel(Vector a,Vector b){
    return eq(cross(a,b),0.0);
}

bool isParallel(Point a1,Point a2,Point b1,Point b2){
    return eq(cross(a1-a2,b1-b2),0.0);
}

bool isParallel(Segment a,Segment b){
    return eq(cross(a.p1-a.p2,b.p1-b.p2),0.0);
}

//射影
Point project(Segment s,Point p){
    Vector base=s.p2-s.p1;
    Real r=dot(p-s.p1,base)/norm(base);
    return s.p1+base*r;
}

Point project(Line l,Point p){
    Vector base=l.p2-l.p1;
    Real r=dot(p-l.p1,base)/norm(base);
    return l.p1+base*r;
}

//反射
Point reflect(Segment s,Point p){
    return p+(project(s,p)-p)*2;
}

//交差判定
bool intersect(const Line& l,const Point& p){
    return abs(ccw(l.p1,l.p2,p))!=1;
}

bool intersect(const Line& l,const Line& m){
    return abs(cross(l.p2-l.p1,m.p2-m.p1))>EPS || abs(cross(l.p2-l.p1,m.p2-l.p1))<EPS;
}

bool intersect(const Segment& s,const Point& p){
    return abs(ccw(s.p1,s.p2,p))==0;
}

bool intersect(const Line& l,const Segment& s){
    return cross(l.p2-l.p1,s.p1-l.p1)*cross(l.p2-l.p1,s.p2-l.p1)<EPS;
}

Real getDistance(const Line& l,const Point& p);

/*bool intersect(const Circle& c,const Line& l){
    return getDistance(l,c.a)<=c.r+EPS;
}

bool intersect(const Circle& c,const Point& p){
    return abs(abs(c.a-p)-c.r)<EPS;
}*/

bool intersect(const Segment& s,const Segment& t){
    return ccw(s.p1,s.p2,t.p1)*ccw(s.p1,s.p2,t.p2)<=0 && ccw(t.p1,t.p2,s.p1)*ccw(t.p1,t.p2,s.p2)<=0;
}

/*int intersect(const Circle& c,const Segment& s){
    if(norm(project(s,c.a)-c.a)-c.r*c.r>EPS)return 0;
    auto d1=abs(c.a-s.p1),d2=abs(c.a-s.p2);
    if(d1<c.r+EPS && d2<c.r+EPS)return 0;
    if(d1<c.r-EPS && d2>c.r+EPS || d1>c.r+EPS && d2<c.r-EPS)return 1;
    const Point p=project(s,c.a);
    if(dot(s.p1-p,s.p2-p)<0)return 2;
    return 0;
}

int intersect(const Circle& c1,const Circle& c2){
    if(c1.r<c2.r)swap(c1,c2);
    Real d=abs(c1.a-c2.a);
    if(c1.r+c2.r<d)return 4;//お互いの円は離れていて接していない
    if(eq(c1.r+c2.r,d))return 3;//円は一箇所で接している
    if(c1.r-c2.r<d)return 2;//交点が二箇所ある
    if(eq(c1.r-c2.r,d))return 1;//片方の円が他方の円を内包していて、一箇所で接している
    return 0;//片方の円が他方の円を内包しているが、接してはいない(交点はない)
}*/

//距離
Real getDistance(const Point& a,const Point& b){
    return abs(a-b);
}

Real getDistance(const Line &l, const Point &p) {
    return abs(p-project(l,p));
}

Real getDistance(const Line& l,const Line& m){
    return (intersect(l,m)?0:getDistance(l,m.p1));
}

Real getDistance(const Segment& s,const Point& p){
    Point t=project(s,p);
    if(intersect(s,t))return abs(p-t);
    else return min(abs(s.p1-p),abs(s.p2-p));
}

Real getDistance(const Segment& s,const Segment& t){
    if(intersect(s,t))return 0;
    return min({getDistance(s,t.p1),getDistance(s,t.p2),getDistance(t,s.p1),getDistance(t,s.p2)});
}

Real getDistance(const Line& l,const Segment& s){
    if(intersect(l,s))return 0;
    return min(getDistance(l,s.p1),getDistance(l,s.p2));
}

//交点計算
Point crosspoint(const Line& l,const Line& m){
    Real a=cross(l.p2-l.p1,m.p2-m.p1);
    Real b=cross(l.p2-l.p1,l.p2-m.p1);
    if(eq(a,0.0) && eq(b,0.0))return m.p1;
    return m.p1+(m.p2-m.p1)*b/a;
}

Point crosspoint(const Segment& s,const Segment& t){
    return crosspoint(Line(s),Line(t));
}

//Shortest_Path
//グラフの最短距離を求めるアルゴリズムを3種類持っているクラスです
class shortest_path{
public:
    
    //dijkstra法とBellman_Ford法を使うときは、このコンストラクタを使ってください
    explicit shortest_path(int n):vertex(n),INF((double)1e9){
        v1.resize(static_cast<unsigned long>(vertex));
    }
    
    //Warshall_Floyd法を使うときは、こちらのコンストラクタを使ってください
    shortest_path(int n,double inf):vertex(n),INF(inf){
        v2.resize(static_cast<unsigned long>(vertex));
        for(int i=0;i<vertex;i++)v2[i].resize(static_cast<unsigned long>(vertex));
        for(int i=0;i<vertex;i++){
            for(int j=0;j<vertex;j++){
                v2[i][j]=INF;
            }
        }
        for(int i=0;i<vertex;i++)v2[i][i]=0;
    }
    
    //dijkstra法とBellman_Ford法専用のadd_edge(int from,int to,ll cost)です
    //コストcostの頂点fromから頂点toへの有向辺を追加するときadd_edge(int from,int to,ll cost)
    void add_edge(int from,int to,double cost){
        v1[from].push_back({to,cost});
    }
    
    //Warshall_Floyd法専用のadd_edge(int from,int to,ll cost)です
    //コストcostの頂点fromから頂点toへの有向辺を追加するときadd_edge(int from,int to,ll cost)
    void add_edge_(int from,int to,ll cost){//warshall_floyd
        v2[from][to]=cost;
    }
    
    //Dijkstra法です
    //各頂点への距離が格納されたvector<ll>が求まります
    //負のコストの辺がある場合は使えません
    //start地点の頂点番号を引数に入れてください
    vector<double> dijkstra(unsigned int start){
        vector<double> d(static_cast<unsigned long>(vertex),INF);
        priority_queue<pair<double,int> > q;
        d[start]=0;
        q.push({0,start});
        while(!q.empty()){
            int now=q.top().se;
            double now_cost=-q.top().fi;
            q.pop();
            if(d[now]<now_cost)continue;
            for (auto &i : v1[now]) {
                if(d[i.fi]>now_cost+ i.se){
                    d[i.fi]=now_cost+ i.se;
                    q.push({-d[i.fi], i.fi});
                }
            }
        }
        return d;
    }
    
    //Warshall_Floyd法です
    //各頂点への距離が格納されたvector<ll>と閉路があるかどうかの情報の2つのtupleが返されます
    //閉路があるとき、返り値はtrueです
    tuple<vector<vector<ll> >,bool> warshall_floyd(){
        for(int k=0;k<vertex;k++){
            for(int i=0;i<vertex;i++){
                if(v2[i][k]==INF)continue;
                for(int j=0;j<vertex;j++){
                    if(v2[k][j]==INF)continue;
                    v2[i][j]=min(v2[i][j],v2[i][k]+v2[k][j]);
                }
            }
        }
        bool is_negative_cycle=false;
        for(int i=0;i<vertex;i++){
            if(v2[i][i]<0)is_negative_cycle=true;
        }
        return make_tuple(v2,is_negative_cycle);
    }

    //Bellman_Ford法です
    //各頂点への距離が格納されたvector<ll>と閉路があるかどうかの情報の2つのtupleが返されます
    //閉路があるとき、返り値はtrueです
    //start地点の頂点番号を引数に入れてください
    tuple<vector<ll>,bool> bellman_ford(int start){
        vector<ll> d(static_cast<unsigned long>(vertex),INF);
        d[start]=0;
        bool is_negative_cycle=false;
        for(int i=0;i<vertex;i++){
            bool update= false;
            for(int j=0;j<vertex;j++){
                if(d[j]==INF)continue;
                for(int k=0;k<(int)v1[j].size();k++){
                    if(d[v1[j][k].fi]>d[j]+v1[j][k].se){
                        d[v1[j][k].fi]=d[j]+v1[j][k].se;
                        update= true;
                    }
                }
            }
            if(i==vertex-1 && update)is_negative_cycle=true;
            else if(!update)break;
        }
        return make_tuple(d,is_negative_cycle);
    }
private:
    double INF;
    int vertex;
    vector<vector<pair<int,double> > > v1;
    vector<vector<ll> > v2;
};
//tuple tp<int,int,int> -> int a=get<0>(tp),b=get<1>(tp),c=get<2>(tp)

int na,nb;
double xa[1001],ya[1001],xb[1001],yb[1001];

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout<<fixed;
#ifdef LOCAL_DEFINE
  FILE *stream1;
  //FILE *stream2;
  stream1=freopen("in","r",stdin);
  //stream2=freopen("out","w",stdout);
  if(stream1==NULL)return 0;
  //if(stream2==NULL)return 0;
#endif
  int na,nb;
  cin>>na>>nb;
  for(int i=0;i<na;i++){
    cin>>xa[i]>>ya[i];
  }
  for(int i=0;i<nb;i++){
    cin>>xb[i]>>yb[i];
  }
  Point tmp(xb[0],yb[0]);
  Point tmp2(xb[1],yb[1]);
  Segment s1(tmp,tmp2);
  shortest_path sp1(na);
  //cout<<1<<endl;
  for(int i=0;i<na;i++){
    for(int j=i+1;j<na;j++){
      Point a(xa[i],ya[i]);
      Point b(xa[j],ya[j]);
      Segment aa(a,b);
      //cout<<aa.p1<<" "<<aa.p2<<endl;
      if(!intersect(s1,aa)){
        //cout<<i<<"--"<<j<<endl;
        sp1.add_edge(i,j,sqrt((xa[i]-xa[j])*(xa[i]-xa[j])+(ya[i]-ya[j])*(ya[i]-ya[j])));
        sp1.add_edge(j,i,sqrt((xa[i]-xa[j])*(xa[i]-xa[j])+(ya[i]-ya[j])*(ya[i]-ya[j])));
      }
    }
  }
  vector<double> di1=sp1.dijkstra(0);
  double ans;
  if(di1[1]!=1e9){
    ans=di1[1]+getDistance(tmp,tmp2);
  }else{
    ans=inf;
  }
  Point tmp3(xa[0],ya[0]);
  Point tmp4(xa[1],ya[1]);
  Segment s2(tmp3,tmp4);
  shortest_path sp2(nb);
  //cout<<2<<endl;
  for(int i=0;i<nb;i++){
    for(int j=i+1;j<nb;j++){
      Point a(xb[i],yb[i]);
      Point b(xb[j],yb[j]);
      Segment aa(a,b);
      if(!intersect(s2,aa)){
        //cout<<i<<"--"<<j<<endl;
        sp2.add_edge(i,j,sqrt((xb[i]-xb[j])*(xb[i]-xb[j])+(yb[i]-yb[j])*(yb[i]-yb[j])));
        sp2.add_edge(j,i,sqrt((xb[i]-xb[j])*(xb[i]-xb[j])+(yb[i]-yb[j])*(yb[i]-yb[j])));
      }
    }
  }
  vector<double> di2=sp2.dijkstra(0);
  if(di2[1]!=inf){
    ans=min(ans,di2[1]+getDistance(tmp3,tmp4));
  }else{
    ans=min(ans,inf);
  }
  if(ans!=inf){
    printf("%.12f\n",ans);
  }else{
    cout<<-1<<endl;
  }
#ifdef LOCAL_DEFINE
  cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}