// template {{{

#include <bits/stdc++.h>
using namespace std;

#define loop(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) loop(i, 0, n)
#define rloop(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); i--)
#define rrep(i, n) rloop(i, 0, n)
#define pb push_back
#define pf push_front
#define eb emplace_back
#define ef emplace_front
#define all(c) std::begin(c), std::end(c)
#define mp std::make_pair
#define mt std::make_tuple
#define fi first
#define se second
#define popcnt __builtin_popcountll

using uint = std::uint32_t;
using ll = std::int64_t;
using ull = std::uint64_t;
using ld = long double;

template<typename T, size_t H, size_t W>
using matrix = std::array<std::array<T, W>, H>;

const int MOD = 1e9 + 7;
const int INF = 1e9 + 10;
const ll LLINF = 1e18 + 10;

const int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
const int dy[] = {0, -1, 0, 1, -1, 1, -1, 1};

template<typename T>
inline T sq(T x){ return x * x; }

template<typename T, typename U>
inline bool chmax(T &x, U y){ if (x >= y) return false; x = y; return true; }

template<typename T, typename U>
inline bool chmin(T &x, U y){ if (x <= y) return false; x = y; return true; }

template<typename T>
inline void sort(T &c){ std::sort(all(c)); }

template<typename T>
inline void reverse(T &c){ std::reverse(all(c)); }

template<typename T>
inline void unique(T &c){ std::sort(c); c.erase(std::unique(all(c)), std::end(c)); }

// }}}
// geometry {{{
using Real = long double;

struct Point {
	Real x, y;
	Point(){}
	Point(Real x, Real y): x(x), y(y){}
	
	const Point operator + (const Point &r) const {
		return Point(x + r.x, y + r.y);
	}
	
	const Point operator - (const Point &r) const {
		return Point(x - r.x, y - r.y);
	}
	
	const Point operator * (Real r) const {
		return Point(x * r, y * r);
	}

	const Point operator * (const Point &r) const {
		return Point(x * r.x - y * r.y, x * r.y + y * r.x);
	}
	
	const Point operator / (Real r) const {
		return Point(x / r, y / r);
	}
	
	Point& operator += (const Point &r){
		x += r.x;
		y += r.y;
		return *this;
	}
	
	Point& operator -= (const Point &r){
		x -= r.x;
		y -= r.y;
		return *this;
	}
	
	Point& operator *= (Real r){
		x *= r;
		y *= r;
		return *this;
	}

	Point& operator *= (const Point &r){
		return *this = *this * r;
	}
	
	Point& operator /= (Real r){
		x /= r;
		y /= r;
		return *this;
	}

	bool operator < (const Point &r) const {
		if (x != r.x) return x < r.x;
		return y < r.y;
	}
};

using LS = array<Point, 2>;

struct Line : LS {
	Line(){}
	Line(const Point &p1, const Point &p2){
		(*this)[0] = p1;
		(*this)[1] = p2;
	}
	Line(const LS &r){
		*this = r;
	}
};

struct Segment : LS {
	Segment(){}
	Segment(const Point &p1, const Point &p2){
		(*this)[0] = p1;
		(*this)[1] = p2;
	}
	Segment(const LS &r){
		*this = r;
	}
};

struct Circle {
	Circle(){}
	Circle(const Point &p, Real r): p(p), r(r){}
	Point p;
	Real r;
};

using Polygon = vector<Point>;

const Real PI = acos(Real(-1));
const Real EPS = 1e-12;

int sgn(Real a){
	if (abs(a) < EPS) return 0;
	if (a < 0.0) return -1;
	return 1;
}

bool eq(Real a, Real b){
	return sgn(a - b) == 0;
}

bool neq(Real a, Real b){
	return sgn(a - b) != 0;
}

bool lt(Real a, Real b){
	return sgn(a - b) < 0;
}

bool leq(Real a, Real b){
	return sgn(a - b) <= 0;
}

bool gt(Real a, Real b){
	return sgn(a - b) > 0;
}

bool geq(Real a, Real b){
	return sgn(a - b) >= 0;
}

Real toRad(Real t){
	return t / 180 * PI;
}

Real toDeg(Real t){
	return t * 180 / PI;
}

Real norm(const Point &a){
	return sq(a.x) + sq(a.y);
}

Real abs(const Point &a){
	return sqrt(norm(a));
}

Real arg(const Point &a){
	return atan2(a.y, a.x);
}

Point polar(Real r, Real t){
	return Point(cos(t) * r, sin(t) * r);
}

Real dot(const Point &a, const Point &b){
	return a.x * b.x + a.y * b.y;
}

Real cross(const Point &a, const Point &b){
	return a.x * b.y - a.y * b.x;
}

int ccw(const Point &p1, const Point &p2, const Point &p3){
	Point a = p2 - p1, b = p3 - p1;
	if (gt(cross(a, b), 0)) return 1;
	if (lt(cross(a, b), 0)) return -1;
	if (lt(dot(a, b), 0)) return 2;
	if (lt(norm(a), norm(b))) return -2;
	return 0;
}

bool orthogonal(const LS &l1, const LS &l2){
	return eq(dot(l1[1] - l1[0], l2[1] - l2[0]), 0);
}

bool parallel(const LS &l1, const LS &l2){
	return eq(cross(l1[1] - l1[0], l2[1] - l2[0]), 0);
}

Point project(const LS &l, const Point &p){
	Real r = dot(p - l[0], l[1] - l[0]) / norm(l[1] - l[0]);
	return l[0] + (l[1] - l[0]) * r;
}

Point reflect(const LS &l, const Point &p){
	return p + (project(l, p) - p) * 2;
}

bool intersect(const Line &l1, const Line &l2){
	if (!parallel(l1, l2)) return true;
	return eq(cross(l1[1] - l1[0], l2[0] - l1[0]), 0);
}

bool intersect(const Line &l, const Segment &s){
	return leq(cross(l[1] - l[0], s[0] - l[0]) * cross(l[1] - l[0], s[1] - l[0]), 0);
}

bool intersect(const Line &l, const Point &p){
	return eq(cross(l[1] - p, l[0] - p), 0);
}

bool intersect(const Segment &s1, const Segment &s2){
	return ccw(s1[0], s1[1], s2[0]) * ccw(s1[0], s1[1], s2[1]) <= 0 &&
	       ccw(s2[0], s2[1], s1[0]) * ccw(s2[0], s2[1], s1[1]) <= 0;
}

bool intersect(const Segment &s, const Point &p){
	return ccw(s[0], s[1], p) == 0;
}

Real distance(const Line &l, const Point &p){
	return abs(cross(l[1] - l[0], p - l[0]) / abs(l[1] - l[0]));
}

Real distance(const Segment &s, const Point &p){
	if (dot(s[1] - s[0], p - s[0]) < 0.0) return abs(p - s[0]);
	if (dot(s[0] - s[1], p - s[1]) < 0.0) return abs(p - s[1]);
	return distance(Line(s), p);
}

Real distance(const Segment &s1, const Segment &s2){
	if (intersect(s1, s2)) return 0.0;
	return min({
		distance(s1, s2[0]), distance(s1, s2[1]),
		distance(s2, s1[0]), distance(s2, s1[1])
	});
}

Point crossPoint(const LS &s1, const LS &s2){
	Real d1 = abs(cross(s2[1] - s2[0], s1[0] - s2[0]));
	Real d2 = abs(cross(s2[1] - s2[0], s1[1] - s2[0]));
	Real t = d1 / (d1 + d2);
	return s1[0] + (s1[1] - s1[0]) * t;
}
// }}}

using pr = pair<Real, int>;

int na, nb;
Real xa[1000], ya[1000], xb[1000], yb[1000];
Real da[1000], db[1000];

int main()
{
	cin >> na >> nb;
	rep(i, na) cin >> xa[i] >> ya[i];
	rep(i, nb) cin >> xb[i] >> yb[i];
	
	priority_queue<pr, vector<pr>, greater<pr>> pq;

	fill_n(da, 1000, 1e9);
	da[0] = 0.0;
	pq.emplace(0.0, 0);
	while (pq.size()){
		int v;
		Real sum;
		tie(sum, v) = pq.top(); pq.pop();
		if (da[v] < sum) continue;
		rep(to, na){
			if (v == to) continue;
			Segment s(Point(xa[v], ya[v]), Point(xa[to], ya[to]));
			Segment t(Point(xb[0], yb[0]), Point(xb[1], yb[1]));
			if (intersect(s, t)) continue;
			Real cost = abs(s[1] - s[0]);
			if (da[to] > sum + cost){
				da[to] = sum + cost;
				pq.emplace(sum + cost, to);
			}
		}
	}

	fill_n(db, 1000, 1e9);
	db[0] = 0.0;
	pq.emplace(0.0, 0);
	while (pq.size()){
		int v;
		Real sum;
		tie(sum, v) = pq.top(); pq.pop();
		if (db[v] < sum) continue;
		rep(to, nb){
			if (v == to) continue;
			Segment s(Point(xb[v], yb[v]), Point(xb[to], yb[to]));
			Segment t(Point(xa[0], ya[0]), Point(xa[1], ya[1]));
			if (intersect(s, t)) continue;
			Real cost = abs(s[1] - s[0]);
			if (db[to] > sum + cost){
				db[to] = sum + cost;
				pq.emplace(sum + cost, to);
			}
		}
	}
	
	Segment s(Point(xa[0], ya[0]), Point(xa[1], ya[1]));
	Segment t(Point(xb[0], yb[0]), Point(xb[1], yb[1]));
	Real res = 1e9;
	chmin(res, abs(s[1] - s[0]) + db[1]);
	chmin(res, abs(t[1] - t[0]) + da[1]);
	if (res == 1e9) cout << -1 << endl;
	else printf("%.20Lf\n", res);
}
### Prompt

Generate a Cpp solution to the following 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

### Response

```cpp
// template {{{

#include <bits/stdc++.h>
using namespace std;

#define loop(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) loop(i, 0, n)
#define rloop(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); i--)
#define rrep(i, n) rloop(i, 0, n)
#define pb push_back
#define pf push_front
#define eb emplace_back
#define ef emplace_front
#define all(c) std::begin(c), std::end(c)
#define mp std::make_pair
#define mt std::make_tuple
#define fi first
#define se second
#define popcnt __builtin_popcountll

using uint = std::uint32_t;
using ll = std::int64_t;
using ull = std::uint64_t;
using ld = long double;

template<typename T, size_t H, size_t W>
using matrix = std::array<std::array<T, W>, H>;

const int MOD = 1e9 + 7;
const int INF = 1e9 + 10;
const ll LLINF = 1e18 + 10;

const int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
const int dy[] = {0, -1, 0, 1, -1, 1, -1, 1};

template<typename T>
inline T sq(T x){ return x * x; }

template<typename T, typename U>
inline bool chmax(T &x, U y){ if (x >= y) return false; x = y; return true; }

template<typename T, typename U>
inline bool chmin(T &x, U y){ if (x <= y) return false; x = y; return true; }

template<typename T>
inline void sort(T &c){ std::sort(all(c)); }

template<typename T>
inline void reverse(T &c){ std::reverse(all(c)); }

template<typename T>
inline void unique(T &c){ std::sort(c); c.erase(std::unique(all(c)), std::end(c)); }

// }}}
// geometry {{{
using Real = long double;

struct Point {
	Real x, y;
	Point(){}
	Point(Real x, Real y): x(x), y(y){}
	
	const Point operator + (const Point &r) const {
		return Point(x + r.x, y + r.y);
	}
	
	const Point operator - (const Point &r) const {
		return Point(x - r.x, y - r.y);
	}
	
	const Point operator * (Real r) const {
		return Point(x * r, y * r);
	}

	const Point operator * (const Point &r) const {
		return Point(x * r.x - y * r.y, x * r.y + y * r.x);
	}
	
	const Point operator / (Real r) const {
		return Point(x / r, y / r);
	}
	
	Point& operator += (const Point &r){
		x += r.x;
		y += r.y;
		return *this;
	}
	
	Point& operator -= (const Point &r){
		x -= r.x;
		y -= r.y;
		return *this;
	}
	
	Point& operator *= (Real r){
		x *= r;
		y *= r;
		return *this;
	}

	Point& operator *= (const Point &r){
		return *this = *this * r;
	}
	
	Point& operator /= (Real r){
		x /= r;
		y /= r;
		return *this;
	}

	bool operator < (const Point &r) const {
		if (x != r.x) return x < r.x;
		return y < r.y;
	}
};

using LS = array<Point, 2>;

struct Line : LS {
	Line(){}
	Line(const Point &p1, const Point &p2){
		(*this)[0] = p1;
		(*this)[1] = p2;
	}
	Line(const LS &r){
		*this = r;
	}
};

struct Segment : LS {
	Segment(){}
	Segment(const Point &p1, const Point &p2){
		(*this)[0] = p1;
		(*this)[1] = p2;
	}
	Segment(const LS &r){
		*this = r;
	}
};

struct Circle {
	Circle(){}
	Circle(const Point &p, Real r): p(p), r(r){}
	Point p;
	Real r;
};

using Polygon = vector<Point>;

const Real PI = acos(Real(-1));
const Real EPS = 1e-12;

int sgn(Real a){
	if (abs(a) < EPS) return 0;
	if (a < 0.0) return -1;
	return 1;
}

bool eq(Real a, Real b){
	return sgn(a - b) == 0;
}

bool neq(Real a, Real b){
	return sgn(a - b) != 0;
}

bool lt(Real a, Real b){
	return sgn(a - b) < 0;
}

bool leq(Real a, Real b){
	return sgn(a - b) <= 0;
}

bool gt(Real a, Real b){
	return sgn(a - b) > 0;
}

bool geq(Real a, Real b){
	return sgn(a - b) >= 0;
}

Real toRad(Real t){
	return t / 180 * PI;
}

Real toDeg(Real t){
	return t * 180 / PI;
}

Real norm(const Point &a){
	return sq(a.x) + sq(a.y);
}

Real abs(const Point &a){
	return sqrt(norm(a));
}

Real arg(const Point &a){
	return atan2(a.y, a.x);
}

Point polar(Real r, Real t){
	return Point(cos(t) * r, sin(t) * r);
}

Real dot(const Point &a, const Point &b){
	return a.x * b.x + a.y * b.y;
}

Real cross(const Point &a, const Point &b){
	return a.x * b.y - a.y * b.x;
}

int ccw(const Point &p1, const Point &p2, const Point &p3){
	Point a = p2 - p1, b = p3 - p1;
	if (gt(cross(a, b), 0)) return 1;
	if (lt(cross(a, b), 0)) return -1;
	if (lt(dot(a, b), 0)) return 2;
	if (lt(norm(a), norm(b))) return -2;
	return 0;
}

bool orthogonal(const LS &l1, const LS &l2){
	return eq(dot(l1[1] - l1[0], l2[1] - l2[0]), 0);
}

bool parallel(const LS &l1, const LS &l2){
	return eq(cross(l1[1] - l1[0], l2[1] - l2[0]), 0);
}

Point project(const LS &l, const Point &p){
	Real r = dot(p - l[0], l[1] - l[0]) / norm(l[1] - l[0]);
	return l[0] + (l[1] - l[0]) * r;
}

Point reflect(const LS &l, const Point &p){
	return p + (project(l, p) - p) * 2;
}

bool intersect(const Line &l1, const Line &l2){
	if (!parallel(l1, l2)) return true;
	return eq(cross(l1[1] - l1[0], l2[0] - l1[0]), 0);
}

bool intersect(const Line &l, const Segment &s){
	return leq(cross(l[1] - l[0], s[0] - l[0]) * cross(l[1] - l[0], s[1] - l[0]), 0);
}

bool intersect(const Line &l, const Point &p){
	return eq(cross(l[1] - p, l[0] - p), 0);
}

bool intersect(const Segment &s1, const Segment &s2){
	return ccw(s1[0], s1[1], s2[0]) * ccw(s1[0], s1[1], s2[1]) <= 0 &&
	       ccw(s2[0], s2[1], s1[0]) * ccw(s2[0], s2[1], s1[1]) <= 0;
}

bool intersect(const Segment &s, const Point &p){
	return ccw(s[0], s[1], p) == 0;
}

Real distance(const Line &l, const Point &p){
	return abs(cross(l[1] - l[0], p - l[0]) / abs(l[1] - l[0]));
}

Real distance(const Segment &s, const Point &p){
	if (dot(s[1] - s[0], p - s[0]) < 0.0) return abs(p - s[0]);
	if (dot(s[0] - s[1], p - s[1]) < 0.0) return abs(p - s[1]);
	return distance(Line(s), p);
}

Real distance(const Segment &s1, const Segment &s2){
	if (intersect(s1, s2)) return 0.0;
	return min({
		distance(s1, s2[0]), distance(s1, s2[1]),
		distance(s2, s1[0]), distance(s2, s1[1])
	});
}

Point crossPoint(const LS &s1, const LS &s2){
	Real d1 = abs(cross(s2[1] - s2[0], s1[0] - s2[0]));
	Real d2 = abs(cross(s2[1] - s2[0], s1[1] - s2[0]));
	Real t = d1 / (d1 + d2);
	return s1[0] + (s1[1] - s1[0]) * t;
}
// }}}

using pr = pair<Real, int>;

int na, nb;
Real xa[1000], ya[1000], xb[1000], yb[1000];
Real da[1000], db[1000];

int main()
{
	cin >> na >> nb;
	rep(i, na) cin >> xa[i] >> ya[i];
	rep(i, nb) cin >> xb[i] >> yb[i];
	
	priority_queue<pr, vector<pr>, greater<pr>> pq;

	fill_n(da, 1000, 1e9);
	da[0] = 0.0;
	pq.emplace(0.0, 0);
	while (pq.size()){
		int v;
		Real sum;
		tie(sum, v) = pq.top(); pq.pop();
		if (da[v] < sum) continue;
		rep(to, na){
			if (v == to) continue;
			Segment s(Point(xa[v], ya[v]), Point(xa[to], ya[to]));
			Segment t(Point(xb[0], yb[0]), Point(xb[1], yb[1]));
			if (intersect(s, t)) continue;
			Real cost = abs(s[1] - s[0]);
			if (da[to] > sum + cost){
				da[to] = sum + cost;
				pq.emplace(sum + cost, to);
			}
		}
	}

	fill_n(db, 1000, 1e9);
	db[0] = 0.0;
	pq.emplace(0.0, 0);
	while (pq.size()){
		int v;
		Real sum;
		tie(sum, v) = pq.top(); pq.pop();
		if (db[v] < sum) continue;
		rep(to, nb){
			if (v == to) continue;
			Segment s(Point(xb[v], yb[v]), Point(xb[to], yb[to]));
			Segment t(Point(xa[0], ya[0]), Point(xa[1], ya[1]));
			if (intersect(s, t)) continue;
			Real cost = abs(s[1] - s[0]);
			if (db[to] > sum + cost){
				db[to] = sum + cost;
				pq.emplace(sum + cost, to);
			}
		}
	}
	
	Segment s(Point(xa[0], ya[0]), Point(xa[1], ya[1]));
	Segment t(Point(xb[0], yb[0]), Point(xb[1], yb[1]));
	Real res = 1e9;
	chmin(res, abs(s[1] - s[0]) + db[1]);
	chmin(res, abs(t[1] - t[0]) + da[1]);
	if (res == 1e9) cout << -1 << endl;
	else printf("%.20Lf\n", res);
}
```