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<iostream>
#include<cstdio>
#include<cfloat>
#include<cassert>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>

using namespace std;

#define EPS (1e-12)
#define equals(a, b) (fabs((a) - (b)) < EPS )
#define dle(a, b) (equals(a, b) || a < b )

static const double PI = acos(-1);

class Point{
    public:
    double x, y;
    
    Point ( double x = 0, double y = 0): x(x), y(y){}
    
    Point operator + ( Point p ){ return Point(x + p.x, y + p.y); }
    Point operator - ( Point p ){ return Point(x - p.x, y - p.y); }
    Point operator * ( double a ){ return Point(x*a, y*a); }
    Point operator / ( double a ){ return Point(x/a, y/a); }
    Point operator / ( Point p ) { return Point((x*p.x+y*p.y)/(p.x*p.x+p.y*p.y), (y*p.x-x*p.y)/(p.x*p.x+p.y*p.y)); }

    double abs() { return sqrt(norm());}
    double norm() { return x*x + y*y; }

    bool operator < ( const Point &p ) const {
	return x != p.x ? x < p.x : y < p.y;
    }

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

typedef Point Vector;

class Segment{
    public:
    Point p1, p2;
  Segment(Point s = Point(), Point t = Point()): p1(s), p2(t){}

};

typedef Segment Line;

static const int CIRCLE_NON = 0;
static const int CIRCLE_OUT = 1;
static const int CIRCLE_IN = 2;
static const int CIRCLE_CROSS = 3;

class Circle{
    public:
    Point c;
    double r;
    Circle(Point c = Point(), double r = 0.0): c(c), r(r){}
};

typedef vector<Point> Polygon;

double norm( Vector a ){ return a.x*a.x + a.y*a.y; }
double abs( Vector a ){ return sqrt(norm(a)); }
Point polar( double a, double r ){ return Point(cos(r)*a, sin(r)*a);}
double getDistance( Vector a, Vector b ){ return abs(a - b); }
double dot( Vector a, Vector b ){ return a.x*b.x + a.y*b.y; }
double cross( Vector a, Vector b ){ return a.x*b.y - a.y*b.x; }
double arg(Vector p){ return atan2(p.y, p.x); }

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

Point reflect( Segment s, Point p ){
    return p + (project(s, p) - p)*2.0;
}

bool isOnSegment( Point a, Point b, Point c){
    if ( a == c || b == c ) return true;
    return (abs(a-c) + abs(c-b) < abs(a-b) + EPS );
}


bool isParallel( Vector a, Vector b ){
    return equals( cross(a, b), 0.0 );
}

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

bool isParallel( Segment s1, Segment s2 ){
    return equals( cross(s1.p2 - s1.p1, s2.p2 - s2.p1), 0.0 );
}

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;

// EPS can be 0
// need to check for 920, 833, 866
int ccw( Point p0, Point p1, Point p2 ){
    Vector a = p1 - p0;
    Vector b = p2 - p0;
    if ( cross(a, b) > EPS ) return COUNTER_CLOCKWISE;
    if ( cross(a, b) < -EPS ) return CLOCKWISE;
    if ( dot(a, b) < -EPS ) return ONLINE_BACK;
    if ( norm(a) < norm(b) ) return ONLINE_FRONT;
    return ON_SEGMENT;
}

// intersect Segment p1-p2 and Segment p3-p4 ?
bool isIntersect(Point p1, Point p2, Point p3, Point p4){
    return ( ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 &&
	     ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0 );
}

// intersect Segment s1 and Segment s2 ?
// verified by 920, 833, 866, uoa2062
bool isIntersect(Segment s1, Segment s2){
    return isIntersect(s1.p1, s1.p2, s2.p1, s2.p2);
}

// verified by 920, 833, uoa2062
Point getCrossPoint(Segment s1, Segment s2){
    assert( isIntersect(s1, s2) );
    Vector base = s2.p2 - s2.p1;
    double d1 = abs(cross(base, s1.p1 - s2.p1));
    double d2 = abs(cross(base, s1.p2 - s2.p1));
    double t = d1/(d1 + d2);
    return s1.p1 + (s1.p2 - s1.p1)*t;
}

Point getCrossPointLines( Line s1, Line s2){
    Vector a = s1.p2 - s1.p1;
    Vector base = s2.p2 - s2.p1;
    return s1.p1 + a * cross(base, s2.p1 - s1.p1)/cross(base, a);
}

double getDistanceLP(Line s, Point p){ 
    return abs(cross(s.p2 - s.p1, p - s.p1)/abs(s.p2 - s.p1));
}

// 10514
double getDistance(Segment s, Point p){
    if ( dot(s.p2 - s.p1, p - s.p1) < 0.0 ) return abs(p - s.p1);
    if ( dot(s.p1 - s.p2, p - s.p2) < 0.0 ) return abs(p - s.p2);
    return abs(cross(s.p2 - s.p1, p - s.p1)/abs(s.p2 - s.p1));
}
double getDistance(Segment s1, Segment s2){
    if ( isIntersect(s1, s2) ) return 0.0;
    return min( min(getDistance(s1, s2.p1), getDistance(s1, s2.p2)),
		min(getDistance(s2, s1.p1), getDistance(s2, s1.p2)));
}

bool isIntersect( Circle c1, Line l ){
    double d = getDistanceLP(l, c1.c);
    return ( equals(d, c1.r) || d < c1.r );
}

pair<Point, Point> getTangentPoints(Point p, Circle c){
  double d = abs(c.c - p);
  double t = arg(c.c - p);
  double b = sqrt(d*d - c.r * c.r);
  double a = asin(c.r / d);
  Point p1 = p + polar(b, t + a);
  Point p2 = p + polar(b, t - a);
  return make_pair(p1, p2);
}

int N, D;
Circle C[10];
vector<Point> SX, GX; // contact points
vector<Point> P; // target points

int getNumOfXCircles(Segment s){
  int cnt = 0;
  for ( int i = 0; i < N; i++ ){
    double d = getDistance(s, C[i].c);
    if ( d < C[i].r && !equals(d, C[i].r)) cnt++;
  }
  return cnt;
}

bool inCircle(Point p){
  for ( int i = 0; i < N; i++ ){
    if ( abs(p - C[i].c) < C[i].r && !equals(abs(p-C[i].c), C[i].r) ) return true;
  }
  return false;
}

int main(){
  cin >> N >> D;
  Point S = Point(25, 0);
  Point G = Point(25, 94);

  for ( int i = 0; i < N; i++ ){
    cin >> C[i].c.x >> C[i].c.y >> C[i].r;
  }

  for ( int i = 0; i < N; i++ ){
    pair<Point, Point> cp;
    cp = getTangentPoints(S, C[i]);
    SX.push_back(cp.first);
    SX.push_back(cp.second);
    cp = getTangentPoints(G, C[i]);
    GX.push_back(cp.first);
    GX.push_back(cp.second);
  }

  for ( int i = 0; i < SX.size(); i++ ){
    Line l1 = Line(S, SX[i]);
    for ( int j = 0; j < GX.size(); j++ ){
      Line l2 = Line(G, GX[j]);
      if ( !isParallel(l1, l2) ){
	Point p = getCrossPointLines(l1, l2);
	if ( 0 < p.x && 0 < p.y && p.x < 50 && p.y < 94) P.push_back(p);
      }
    }
  }

  double ans = 10000;
  bool ok = false;

  for ( int i = 0; i < P.size(); i++ ){
    //printf("%.8lf, %.8lf\n", P[i].x, P[i].y);
    int cnt = 0;
    cnt += getNumOfXCircles(Segment(S, P[i]));
    cnt += getNumOfXCircles(Segment(G, P[i]));
    if ( inCircle(P[i]) ) cnt--;

    if ( cnt <= D ){
      ok = true;
      ans = min(ans, abs(P[i]-S) + abs(P[i]-G));
    }
  }

  if ( getNumOfXCircles(Segment(S, G) ) <= D ){
    ans = min(ans, abs(S - G));
    ok = true;
  }

  if ( ok ){
    printf("%.8lf\n", ans);
  } else {
    cout << -1 << endl;
  }
			  
  return 0;
}