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;

const double EPS = 1e-8;
const double INF = 1e12;

typedef complex<double> P;

#define X real()
#define Y imag()

#define Curr(P,i) P[(i)%P.size()]
#define Next(P,i) P[(i+1)%P.size()]
#define Prev(P,i) P[(i+P.size()-1)%P.size()]

namespace std{
  bool operator<(const P a,const P b){
    return a.X != b.X ? a.X < b.X : a.Y < b.Y;
  }
}
double cross(const P a,const P b){
  return (conj(a)*b).imag();
}
double dot(const P a,const P b){
  return (conj(a)*b).real();
}
// TODO make graph (20)
int ccw(P a,P b,P c){
  b-=a;
  c-=a;
  if(cross(b,c)>0)    return +1;//counter clockwise
  if(cross(b,c)<0)    return -1;//clockwise
  if(dot(b,c)<0)      return +2;// c--a--b
  if(norm(b)<norm(c)) return -2;// a--b--c
                      return  0;// a--c--b(or b==c)
}

struct L : public vector<P>{
  L(const P a,const P b){
    push_back(a),push_back(b);
  }
};
typedef L S;
typedef vector<P> G;

struct C{
  P p;double r;
  C(const P p,double r): p(p),r(r){}
};



//直線と点の関係
P projection(L a,P p){
  double t = dot(p-a[0],a[0]-a[1])/norm(a[0]-a[1]);
  return a[0] + t*(a[0]-a[1]);
}
P reflection(L a,P p){
  return p + 2.0 * (projection(a,p)-p);
}




//交差判定
//TODO CP(内包) CL CS (0)
bool isCrossLL(L a,L b){
  return 
    abs(cross(a[1]-a[0],b[1]-b[0])) > EPS
    || abs(cross(a[1]-a[0],b[0]-a[0])) < EPS ;
}
bool isCrossLS(L a,S b){
  return 
    cross(a[1]-a[0],b[0]-a[0]) 
    * cross(a[1]-a[0],b[1]-a[0]) < EPS;
}
bool isCrossLP(L l,P p){
  return abs(cross(l[1]-p,l[0]-p)) < EPS;
}
bool isCrossSS(S a,S b){
  return
    ccw(a[0],a[1],b[0])
    * ccw(a[0],a[1],b[0]) <= 0
    &&
    ccw(b[0],b[1],a[0])
    * ccw(b[0],b[1],a[0]) <= 0;
}
bool isCrossSP(S a,P p){
  return abs(a[0]-p)+abs(a[1]-p)-abs(a[0]-a[1]) < EPS;
}


// 距離 CP CL CS は(distXP(x,c.p)-c.r)
double distPP(P a,P b){
  return abs(a-b);
}
double distLP(L a,P p){
  return abs(p-projection(a,p));
}
double distLL(L a,L b){
  return isCrossLL(a,b) ? 0 : distLP(a,b[0]);
}
double distLS(L a,S b){
  return isCrossLS(a,b) ? 0 : min(distLP(a,b[0]),distLP(a,b[1]));
}
double distSP(S a,P p){
  const P r = projection(a,p);
  return isCrossSP(a,r) ? abs(p-r) : min(abs(a[0]-p),abs(a[1]-p));
}
double distSS(S a,S b){
  return isCrossSS(a,b)?0:
    min(
      min(distSP(a,b[0]),distSP(a,b[0])),
      min(distSP(a,b[0]),distSP(a,b[0]))
    );
}

//円の交差判定
bool isCrossCP(C a,P p){
  return abs(a.p-p)-a.r<=EPS;
}
bool isCrossCL(C a,L l){
  return distLP(l,a.p)-a.r<EPS;
}
double distSP_MAX(S a,P p){
  return max(abs(a[0]-p),abs(a[1]-p));
}
bool isCrossCS(C a,S s){
  return distSP(s,a.p)-a.r<-EPS&&distSP_MAX(s,a.p)-a.r>+EPS;
}
bool isCrossCC(C a,C b){//接してる時は交差
  return abs(a.p-b.p)-(a.r+b.r) <= EPS;
}


//交差点
//先に交差判定をすること
P crossP_LL(L a,L b){
  double A = cross(a[1]-a[0],b[1]-b[0]);
  double B = cross(a[1]-a[0],a[1]-b[0]);
  if(abs(A)<EPS && abs(B)<EPS)return b[0];
  if(abs(A)<EPS)assert(false);
  return b[0]+B/A*(b[1]-b[0]);
}
vector<P> crossP_CL(C c,L l){
  P tmp = projection(l,c.p);
  P e = (l[0]-l[1])/abs(l[0]-l[1]);
  double h = abs(c.p-tmp)*abs(c.p-tmp);
  double t = sqrt(c.r*c.r - h*h);
  if(t<EPS)return {tmp};
  return {tmp + e*t,tmp - e*t};
}
vector<P> crossP_CC(C a,C b){
  P A = conj(a.p-b.p);
  P B = (b.r*b.r - a.r*a.r - (b.p-a.p)*conj(b.p-a.p));
  P C = a.r*a.r*(a.p-b.p);
  P D = B*B-4.0*A*C;
  P z1 = (-B+sqrt(D))/(2.0*A)+a.p;
  P z2 = (-B+sqrt(D))/(2.0*A)+b.p;
  return {z1,z2};
}



//三点->円
P PPPtoC(P a,P b,P c){
  P x = 1.0/(conj(b-a));
  P y = 1.0/(conj(c-a));
  return (y-x)/( conj(x)*y - x*conj(y) ) + a;
}

//凸包
G convex_hull(G ps){
  int n = ps.size();
  int k = 0;
  G ch(2*n);
  for(int i = 0;i<n;(ch[k++]=ps[i++])){
    while(k>=2&&ccw(ch[k-2],ch[k-1],ps[i])<=0)--k;
  }
  for(int i = n-2,t=k+1 ; i>=0 ; ch[k++]=ps[i--]){
    while(k>=t && ccw(ch[k-2],ch[k-1],ps[i])<=0)--k;
  }
  ch.resize(k-1);
  return ch;
} 


//凸性判定
bool isConvex(G g){
  for(int i=0; i<g.size();i++){
    if(ccw(Prev(g,i),Curr(g,i),Next(g,i))>0)return false;
  }
}



//接線
//TODO check
vector<L> TLine_CP(C c,P p){
  P v = c.p - p;
  double t = asin(abs(c.r)/(abs(v)));
  P e = v/abs(v) * exp(P(.0,t));
  P n1 = sqrt(abs(v)*abs(v) - c.r*c.r)*e + p;
  P n2 = reflection(L(p,c.p),n1);
  return {L(p,n1),L(p,n2)};
}

// TLine CC
vector<L> TLine_CPr(C c,P p,double r){
  P v = c.p - p;
  double t = asin(abs(c.r)/(abs(v)));
  P e = v/abs(v) * exp(P(.0,t));
  P n1 = sqrt(abs(v)*abs(v) - c.r*c.r)*e + p;
  P e1 = (n1-c.p)/abs(n1-c.p) * r;
  P n2 = reflection(L(p,c.p),n1);
  P e2 = (n2-c.p)/abs(n2-c.p) * r;
  return {L(p+e1,n1+e1),L(p+e2,n2+e2)};
}
vector<L> TLine_CC(C a,C b){
  //接してる時がヤバイ
  vector<L> res;
  if(!isCrossCC(a,b)&&(abs(a.r)>EPS)&&(abs(b.r>EPS))){
    P tmp = (a.p-b.p)*(b.r)/(a.r+b.r) + b.p;
    auto t1 = TLine_CP(a,tmp);
    auto t2 = TLine_CP(b,tmp);
    res.push_back(L(t1[0][1],t2[0][1]));
    res.push_back(L(t1[1][1],t2[1][1]));
  }
  if(abs(a.r-b.r)<EPS){
    const auto r = a.r;
    P e = (a.p-b.p)/abs(a.p-b.p) * exp(P(.0,90.0/180.0*M_PI));
    res.push_back(L(a.p+(e*r),b.p+(e*r)));
    if(abs(r)>=EPS)res.push_back(L(a.p-(e*r),b.p-(e*r)));
  }else{
    if(a.r<b.r)swap(a,b);
    auto t3 = TLine_CPr(C(a.p,a.r-b.r),b.p,b.r);
    for(auto i:t3){
      res.push_back(i);
    }
  }
  return res;
}
int d;
vector<C> in;
void init(){
  in.clear();
}
int input(){
  int n;
  cin>>n>>d;
  if(cin.eof())return false;
  for(int i=0;i<n;i++){
    double x,y,r;
    cin>>x>>y>>r;
    in.push_back(C{P{x,y},r});
  }
  return true;
}

bool inside(P a){
  return -EPS<a.X&&a.X<50+EPS&&-EPS<a.Y&&a.Y<94+EPS;
}


double solve(){
  vector<L> sl;
  vector<L> gl;
  const P s(25,0);
  const P g(25,94);
  for(int i=0;i<in.size();i++){
    vector<L> tmp = TLine_CP(in[i],s);
    for(auto i:tmp){
      sl.push_back(i);
    }
  }
  for(int i=0;i<in.size();i++){
    vector<L> tmp = TLine_CP(in[i],g);
    for(auto i:tmp){
      gl.push_back(i);
    }
  }
  double ans = INF;
  {
    int c = 0;
    for(auto i:in){
      if(isCrossCS(i,L(s,g)))c++;
    }
    if(c<=d)ans= min(ans,distPP(s,g));
  }
  for(auto i:sl){
    for(auto j:gl){
      if(!isCrossLL(i,j))continue;
      P tmp = crossP_LL(i,j);
      if(!inside(tmp))continue;
      pair<S,S> route(L(s,tmp),L(tmp,g));
      int c = 0;
      for(auto i:in){
        if(isCrossCS(i,route.first))c++;
        if(isCrossCS(i,route.second))c++;
        if(isCrossCP(i,tmp))c--;
      }
      if(c>d)continue;
      ans = min(distPP(route.first[0],route.first[1])+distPP(route.second[0],route.second[1]),ans);
    }
  }

  if(abs(ans-INF)<EPS)return -1;
  return ans;
}
int main(){
  while(init(),input()){
    cout<<fixed<<setprecision(10)<<solve()<<endl;
  }
}