Problem: E --Disappear Drive

Story

The person in D likes basketball, but he likes shooting, so other techniques are crazy. I'm not particularly good at dribbling, and when I enter the opponent's defensive range, I always get the ball stolen. So I decided to come up with a deadly dribble that would surely pull out any opponent. After some effort, he finally completed the disappearing drive, "Disapia Drive".

This Apia Drive creates a gap by provoking the opponent to deprive him of his concentration and take his eyes off, and in that gap he goes beyond the wall of dimension and slips through the opponent's defensive range. It's a drive. However, crossing the dimensional wall puts a heavy burden on the body, so there is a limit to the number of times the dimensional wall can be crossed. Also, because he always uses his concentration, he can only change direction once, including normal movements. How do you move on the court to reach the goal in the shortest time without being robbed of the ball?

Problem

Consider a rectangle on a two-dimensional plane with (0,0) at the bottom left and (50,94) at the top right. In addition, there are N circles on this plane, the center position of the i-th circle is (x_i, y_i), and the radius is r_i. There is no overlap between the circles.

Let (25,0) be the point S and (25,94) be the point G, and consider the route from S to G. A "path" consists of (1) a line segment connecting S and G, or (2) a combination of a line segment SP and a line segment GP at any point P inside a rectangle. In the middle of the route from S to G, the period from entering the inside of a circle to exiting the inside of the circle is defined as "the section passing through the inside of the circle". However, it is assumed that the circumferences of the rectangle and the circle are not included in the rectangle and the circle, respectively.

Find the length of the shortest route among the routes where the number of sections passing through the inside of the circle is D or less. If you can't reach the goal, return -1.

Input

The input consists of the following format.


N D
x_1 y_1 r_1
...
x_N y_N r_N

The first line consists of two integers, and the number N of circles and the number of times D that can pass inside the circle are given, separated by one blank character. The following N lines are given circle information. The i + 1 line (1 \ leq i \ leq N) consists of three integers, and the x-coordinate x_i, y-coordinate y_i, and radius r_i of the center of the i-th circle are given by separating them with one blank character.

Constraints:

* 0 \ leq N \ leq 5
* 0 \ leq D \ leq 5
* 0 \ leq x_i \ leq 50
* 0 \ leq y_i \ leq 94
* 1 \ leq r_i \ leq 100
* It can be assumed that any two circles are separated by 10 ^ {-5} or more.
* It can be assumed that S and G are not included inside any circle.
* It can be assumed that S and G are separated from any circle by 10 ^ {-5} or more.
* It can be assumed that the point P in the shortest path is more than 10 ^ {-5} away from the circumference of the rectangle and any circumference.



Output

Output the length of the shortest path on one line. Be sure to start a new line at the end of the line. However, if you cannot reach the goal, return -1. Absolute error or relative error of 10 ^ {-7} or less is allowed for the correct answer.

Sample Input 1


Ten
25 47 10

Sample Output 1


96.2027355887

DisappearDrive_sample1.png

The detour route is the shortest because it cannot disappear.

Sample Input 2


1 1
25 47 10

Sample Output 2


94.0000000000

DisappearDrive_sample2.png

It can disappear, so you just have to go straight through it.

Sample Input 3


Ten
20 47 5

Sample Output 3


94.0000000000

DisappearDrive_sample3.png

Since the circumference is not included in the circle, it can pass through without disappearing.

Sample Input 4


Ten
25 47 40

Sample Output 4


-1

DisappearDrive_sample4.png

You can't reach the goal because you can't disappear or detour.

Sample Input 5


5 2
11 10 16
33 40 18
20 66 10
45 79 14
22 85 8

Sample Output 5


96.1320937224

DisappearDrive_sample5.png





Example

Input

1 0
25 47 10


Output

96.2027355887

Solution (in CPP):

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

#define dump(...) (cerr<<#__VA_ARGS__<<" = "<<(DUMP(),__VA_ARGS__).str()<<endl)
struct DUMP : stringstream {
	template<class T>
	DUMP &operator,(const T &t) {
		if(this->tellp()) *this << ", ";
		*this << t;
		return *this;
	}
};

constexpr double EPS = 1e-8;

struct point {
	double x, y;
	point(double x_ = 0, double y_ = 0):x(x_), y(y_) {}
	point(const point &p):x(p.x), y(p.y) {}

	point operator+(const point &p) const {
		return point(x + p.x, y + p.y);
	}

	point operator-(const point &p) const {
		return point(x - p.x, y - p.y);
	}

	point operator*(double s) const {
		return point(x * s, y * s);
	}

	point operator*(const point &p) const {
		return point(x * p.x - y * p.y, x * p.y + y * p.x);
	}

	point operator/(const double s) const {
		return point(x / s, y / s);
	}

	bool operator<(const point &p) const {
		return x + EPS < p.x || (abs(x - p.x) < EPS && y + EPS < p.y);
	}

	bool operator==(const point &p) const {
		return abs(x - p.x) < EPS && abs(y - p.y) < EPS;
	}
};

ostream &operator<<(ostream &os, const point &p) {
	return os << '(' << p.x << ", " << p.y << ')';
}

point rotate90(const point &p) {
	return point(-p.y, p.x);
}

double norm(const point &p) {
	return p.x * p.x + p.y * p.y;
}

double abs(const point &p) {
	return sqrt(norm(p));
}

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

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

struct line {
	point a, b;
	line(const point &a_, const point &b_):a(a_), b(b_) {}
};

struct segment {
	point a, b;
	segment(const point &a_, const point &b_):a(a_), b(b_) {}
};

struct circle {
	point c;
	double r;
	circle(const point &c_, double r_):c(c_), r(r_) {}
};

double dist(const point &a, const point &b) {
	return abs(a - b);
}

double dist(const line &l, const point &p) {
	return abs(cross(l.b - l.a, p - l.a)) / abs(l.b - l.a);
}

double dist(const segment &s, const point &p) {
	if(dot(s.b - s.a, p - s.a) < 0) return dist(p, s.a);
	if(dot(s.a - s.b, p - s.b) < 0) return dist(p, s.b);
	return dist(line(s.a, s.b), p);
}

bool intersect(const circle &c, const point &p) {
	return dist(p, c.c) + EPS < c.r;
}

bool intersect(const circle &c, const segment &s) {
	return dist(s, c.c) + EPS < c.r;
}

point crosspoint(const line &a, const line &b) {
	const double tmp = cross(a.b - a.a, b.b - b.a);
	if(abs(tmp) < EPS) return a.a;
	return b.a + (b.b - b.a) * cross(a.b - a.a, a.a - b.a) / tmp;
}

vector<point> tangent(const circle &c, const point &p) {
	const double x = norm(p - c.c);
	double d = x - c.r * c.r;
	if(d < -EPS) return vector<point>();
	d = max(d, 0.0);
	const point p1 = (p - c.c) * (c.r * c.r / x);
	const point p2 = rotate90((p - c.c) * (-c.r * sqrt(d) / x));
	vector<point> res;
	res.push_back(c.c + p1 - p2);
	res.push_back(c.c + p1 + p2);
	return res;
}

constexpr double W = 50.0;
constexpr double H = 94.0;
constexpr double INF = INT_MAX;

template<class T> inline void chmin(T &a, const T &b) { if(a > b) a = b; }

bool out(const point &p) {
	return p.x < EPS || p.y < EPS || p.x + EPS > W || p.y + EPS > H;
}

vector<line> get_line(const circle &c, const point &p) {
	const auto ts = tangent(c, p);
	vector<line> res;
	for(const auto &t : ts) {
		if(t == p) {
			res.emplace_back(p, p + rotate90(c.c - p));
		}
		else {
			res.emplace_back(p, t);
		}

	}
	return res;
}

int main() {
	const point start(W / 2.0, 0);
	const point goal(W / 2.0, H);

	cout.flags(ios::fixed);
	cout.precision(10);

	int N, D;
	cin >> N >> D;

	vector<circle> circles;
	circles.reserve(N);

	for(int i = 0; i < N; ++i) {
		int x, y, r;
		cin >> x >> y >> r;
		circles.emplace_back(point(x, y), r);
	}

	int cnt = 0;
	for(const auto &c : circles) {
		if(intersect(c, segment(start, goal))) ++cnt;
	}

	if(cnt <= D) {
		cout << 94.0 << endl;
		return 0;
	}

	vector<line> s_lines;
	vector<line> g_lines;
	s_lines.reserve(2 * N);
	g_lines.reserve(2 * N);

	for(const auto &c : circles) {
		auto ls = get_line(c, start);
		s_lines.insert(s_lines.end(), ls.begin(), ls.end());
		ls = get_line(c, goal);
		g_lines.insert(g_lines.end(), ls.begin(), ls.end());
	}

	double ans = INF;
	for(const auto &s_l : s_lines) {
		for(const auto &g_l : g_lines) {
			const point cp = crosspoint(s_l, g_l);
			if(out(cp)) continue;

			const segment s1(start, cp);
			const segment s2(cp, goal);

			cnt = 0;
			for(const auto &c : circles) {
				const bool i1 = intersect(c, s1);
				const bool i2 = intersect(c, s2);

				if(i1 && i2 && !intersect(c, cp)) {
					cnt += 2;
				}
				else if(i1 || i2) {
					++cnt;
				}
			}

			if(cnt <= D) chmin(ans, dist(start, cp) + dist(cp, goal));
		}
	}

	if(ans == INF) {
		puts("-1");
	}
	else {
		cout << ans << endl;
	}

	return 0;
}