Problem: N circles are drawn on the paper. The rabbit has k-colored paint and paints the paper according to the following rules.

* Paint each area with one color of paint or nothing. Here, the "area" refers to the part with a finite area surrounded by a set of arcs.
* Two adjacent areas cannot be painted with the same color. Here, "adjacent" means that there is an arc that shares a part of the boundary. There are a finite number of shared points. Two areas are not considered to be adjacent.
* It is permissible to leave both adjacent areas unpainted.



Rabbit wants to paint as many areas as possible. Find the maximum number of areas that can be painted.



Input

Line 1: n k (1 ≤ n ≤ 20, 1 ≤ k ≤ 1 000 000 000)
Line 2- (n + 1): xi yi ri, (-1 000 ≤ xi, yi ≤ 1 000, 1 ≤ ri ≤ 1 000) (integer)

Neither two circles match.

The point set obtained as the intersection of any two circles does not include two different points with a distance of 10-3 or less.

Output

Output the maximum number of areas that can be painted with paint on one line.

Example

Input

2 1
10 0 10
20 0 10


Output

2

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
#define MAX 32
#define inf 1<<29
#define linf (1e16)
#define eps (1e-10)
#define Eps (1e-15)
#define mod 1000000007
#define pi acos(-1.0)
#define phi (1.0+sqrt(5.0))/2.0
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define pd(a) printf("%.10f\n",(double)(a))
#define pld(a) printf("%.10Lf\n",(ld)(a))
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(a)-1;(b)<=i;i--)
#define Unique(v) v.erase(unique(all(v)),v.end())
#define equals(a,b) (fabs((a)-(b))<eps)
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,double> pid;
typedef pair<double,int> pdi;
typedef pair<double,double> pdd;
typedef vector<int> vi;
typedef vector<pii> vpi;

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 k){ return Point(x*k,y*k);}
  Point operator/(double k){ return Point(x/k,y/k);}
  bool operator<(Point p)const{ 
    return equals(x,p.x) ? y-p.y<-eps : x-p.x<-eps; }
  bool operator==(Point p)const{ 
    return fabs(x-p.x)<eps && fabs(y-p.y)<eps;}

  double abs(){ return sqrt(norm());}
  double norm(){ return (x*x+y*y);}
};
typedef Point Vector;
typedef vector<Point> Polygon;

class Segment{
public:
  Point p1,p2;
  Segment(Point p1=Point(),Point p2=Point()):p1(p1),p2(p2){}
};
typedef Segment Line;

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

double norm(Vector a){ return (a.x*a.x+a.y*a.y);}
double abs(Vector a){ return sqrt(norm(a));}
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);}
Vector polar(double a,double r){ return Point(cos(r)*a,sin(r)*a);}

class Dedge{
  public:
  int s,t,f,l;
  ld r;
  Dedge(int s,int t,ld r):s(s),t(t),f(0),l(0){
    while(pi<r)r-=2.0*pi;
    while(r<-pi)r+=2.0*pi;
    this->r=r;
  }
  bool operator==(Dedge e)const{ return t==e.t; }
  bool operator<(Dedge e)const{ return r>e.r; }
  bool operator<(ld R)const{ return r>R; }
};

class DualGraph{
  public:
  int n;
  vector<Point> v;
  vector<Polygon> P;
  vector<vector<Dedge> > g;

  DualGraph(vector<Point> v):v(v),g(v.size()),n(v.size()){}

  void add_edge(int s,int t){
    ld r=arg(v[t]-v[s]);
    g[s].pb(Dedge(s,t,r));
    g[t].pb(Dedge(t,s,r+pi));
  }

  void add_polygon(int s,int t,ld r){
    vector<Dedge>::iterator e=lower_bound(all(g[s]),r-eps);
    if(e==g[s].end())e=g[s].begin();
    if(e->f)return;
    e->f=1;
    e->l=t;
    P[t].pb(v[s]);
    add_polygon(e->t, t, e->r > 0 ? e->r-pi : e->r+pi);
  }

  vector<Polygon> dual(){
    FOR(i,0,n){ sort(all(g[i])); Unique(g[i]); }
    FOR(i,0,n){
      FOR(j,0,g[i].size()){
        if(!g[i][j].f){
          P.pb(Polygon());
          add_polygon(i,P.size()-1,g[i][j].r+eps);
        }
      }
    }
    return P;
  }
};

bool on(Circle c,Point p){ return equals(abs(c.c-p),c.r); }

int intersect(Circle a,Circle b){
  double d=abs(a.c-b.c);
  if(a.r<b.r)swap(a,b);
  if(a.r+b.r+eps<d)return 2;
  if(a.r+b.r-eps<d)return 1;
  if(a.r-b.r+eps<d)return 0;
  if(a.r-b.r-eps<d)return -1;
  return -2;
}

pair<Point,Point> getCrossPoints(Circle c1,Circle c2){
  double d=abs(c1.c-c2.c);
  double a=acos((c1.r*c1.r+d*d-c2.r*c2.r)/(2.0*c1.r*d));
  double t=arg(c2.c-c1.c);
  return mp(c1.c+polar(c1.r,t+a),c1.c+polar(c1.r,t-a));
}

Point rotate(Point base,Point a,double r){
  Point b=a-base;
  a.x=b.x*cos((r/180.0)*pi)-b.y*sin((r/180.0)*pi);
  a.y=b.x*sin((r/180.0)*pi)+b.y*cos((r/180.0)*pi);
  a=a+base;
  return a;
}

double getAngle(Vector a,Vector b){
  double tmp=dot(a,b)/(abs(a)*abs(b));
  if(tmp<-1.0)tmp=-1.0;
  if(1.0<tmp)tmp=1.0;
  double r=acos(tmp)*180.0/pi;
  if(cross(a,b)<-eps)r=360.0-r;
  return r;
}

double Area(Polygon p){
  double area=0.0;
  int n=p.size();
  for(int i=0;i<n;i++)area+=cross(p[i],p[(i+1)%n]);
  return area/2.0;
}

int contains(Polygon g,Point p){
  int n=g.size();
  bool x=false;
  for(int i=0;i<n;i++){
    Vector a=g[i]-p,b=g[(i+1)%n]-p;
    if(abs(cross(a,b))<eps && dot(a,b)<eps)return 1;
    if(a.y>b.y)swap(a,b);
    if(a.y<eps && eps<b.y && cross(a,b)>eps)x=!x;
  }
  if(x)return 2;
  return 0;
}

vector<Polygon> remove(vector<Polygon> p){
  vector<Polygon> res;
  FOR(i,0,p.size())if(eps<Area(p[i]))res.pb(p[i]);
  return res;
}

void P(Polygon p){
  cout<<endl<<p.size()<<endl;
  FOR(i,0,p.size())cout<<p[i].x<<" "<<p[i].y<<endl;
}

struct edge{ int to,cap,rev; };

int n,k;
vector<Circle> vc;
vector<Polygon> v;
vector<edge> G[2002];
bool used[2002];
bool in[2002][2002];
bool adj[2002][2002];

void add_edge(int from,int to,int cap){
  G[from].push_back((edge){to,cap,(int)G[to].size()});
  G[to].push_back((edge){from,0,(int)G[from].size()-1});
}
 
int dfs(int v,int t,int f){
  if(v==t)return f;
  used[v]=true;
  for(int i=0;i<G[v].size();i++){
    edge &e=G[v][i];
    if(!used[e.to] && e.cap>0){
      int d=dfs(e.to,t,min(f,e.cap));
      if(d>0){
    e.cap-=d;
    G[e.to][e.rev].cap+=d;
    return d;
      }
    }
  }
  return 0;
}
 
int max_flow(int s,int t){
  int flow=0;
  for(;;){
    fill(used,used+2002,0);
    int f=dfs(s,t,inf);
    if(f==0)return flow;
    flow+=f;
  }
}

bool same(Point a,Point b,Point c,Point d){
  return ((a==c && b==d) || (a==d && b==c));
}

bool check1(Polygon a,Polygon b){
  FOR(i,0,a.size())
    FOR(j,0,b.size())
      if(same(a[i],a[(i+1)%a.size()],b[j],b[(j+1)%b.size()]))
        return true;
  return false;
}

bool check2(Polygon a,Polygon b){
  FOR(i,0,a.size())
    if(contains(b,a[i])!=2)return false;
  return true;
}

int cal(){
  int V=v.size();
  int s=2*V,t=s+1;
  FOR(i,0,V){
    add_edge(s,i,1);
    add_edge(i+V,t,1);
  }
  FOR(i,0,V){
    FOR(j,0,V){
      if(i==j)continue;
      adj[i][j]=check1(v[i],v[j]);
      in[i][j]=check2(v[i],v[j]);
//      if(in[i][j])P(v[i]);
    }
  }

  FOR(i,0,V)
    FOR(j,0,V)
      if(in[i][j])
        FOR(k,0,V)
          if(in[i][j] && in[i][k] && in[k][j])
            in[i][j]=false;

  FOR(i,0,V)
    FOR(j,0,V)
      if(adj[i][j] || in[i][j] || in[j][i])add_edge(i,j+V,1);
  return V-max_flow(s,t)/2;
}

int solve(){
  vector<Point> vp,tmp;
  FOR(i,0,n){
    vp.pb(Point(vc[i].c.x+vc[i].r,vc[i].c.y));
    vp.pb(Point(vc[i].c.x-vc[i].r,vc[i].c.y));
    vp.pb(Point(vc[i].c.x,vc[i].c.y+vc[i].r));
    vp.pb(Point(vc[i].c.x,vc[i].c.y-vc[i].r));
    FOR(j,i+1,n){
      if(abs(intersect(vc[i],vc[j]))==2)continue;
      pair<Point,Point> pp=getCrossPoints(vc[i],vc[j]);
      vp.pb(pp.f);
      vp.pb(pp.s);
    }
  }
  FOR(i,0,n){
    vector<pair<double,Point> > list;
    FOR(j,0,vp.size()){
      double rarg=arg(vp[j]-vc[i].c);
      if(rarg<-eps)rarg+=2.0*pi;
      if(on(vc[i],vp[j]))list.pb(mp(rarg,vp[j]));
    }
    sort(all(list));
    FOR(j,0,list.size()){
      Point a=list[j].s,b=list[(j+1)%list.size()].s;
      double r=getAngle(a-vc[i].c,b-vc[i].c);
      tmp.pb(rotate(vc[i].c,a,r/2.0));
    }
  }
  FOR(i,0,tmp.size())vp.pb(tmp[i]);
  sort(all(vp));
  Unique(vp);
  DualGraph dg=DualGraph(vp);
  FOR(i,0,n){
    vector<pair<double,int> > list;
    FOR(j,0,vp.size()){
      double rarg=arg(vp[j]-vc[i].c);
      if(rarg<-eps)rarg+=2.0*pi;
      if(on(vc[i],vp[j]))list.pb(mp(rarg,j));
    }
    sort(all(list));
    FOR(j,0,list.size()){
      int a=list[j].s,b=list[(j+1)%list.size()].s;
      dg.add_edge(a,b);
    }
  }
  v=dg.dual();
  v=remove(v);
  if(1<k)return v.size();
  return cal();
}

int main()
{
  cin>>n>>k;
  vc.resize(n);
  FOR(i,0,n)cin>>vc[i].c.x>>vc[i].c.y>>vc[i].r;
  cout<<solve()<<endl;
  return 0;
}