macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, Chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, Usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}


#[allow(unused)]
#[inline]
fn get_time()->f64{
    static mut START:f64=-1.;
    let t=std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap().as_secs_f64();
    unsafe{
        if START<0.{START=t;}
        t-START
    }
}


#[cfg(local)]
#[allow(unused)]
macro_rules! debug{
    ()=>{
        eprintln!();
    };
    ($x:literal)=>{
        eprintln!("{:?}",$x);
    };
    ($x:expr)=>{
        eprintln!("{}: {:?}",stringify!($x),$x);
    };
    ($x:literal,$($l:expr),*)=>{
        eprint!("{:?}, ",$x);
        debug!($($l),*);
    };
    ($x:expr,$($l:expr),*)=>{
        eprint!("{}: {:?}, ",stringify!($x),$x);
        debug!($($l),*);
    }
}
#[cfg(not(local))]
#[allow(unused)]
macro_rules! debug{
    ($($_:expr),*)=>{}
}


#[allow(unused)]
mod rnd {
    static mut S:usize=88172645463325252;
    #[inline]
    pub fn next()->usize{
        unsafe{
            S^=S<<7;
            S^=S>>9;
            S
        }
    }
    
    #[inline]
    pub fn nextf()->f64{
        unsafe{
            std::mem::transmute::<_,f64>(0x3ff0000000000000|next()&0xfffffffffffff)-1.
        }
    }
    
    // [a,b)
    #[inline]
    pub fn range(a:usize,b:usize)->usize{
        next()%(b-a)+a
    }

    #[inline]
    pub fn rangei(a:i64,b:i64)->i64{
        (next()>>1) as i64%(b-a)+a
    }

    #[inline]
    pub fn shuffle<T>(list:&mut [T]){
        for i in (0..list.len()).rev(){
            list.swap(i,next()%(i+1));
        }
    }
}


const N:usize=100;
const M:usize=8;
const A:i64=5;


#[inline]
fn get_dist(p1:(usize,usize),p2:(usize,usize))->i64{
    let y=p1.0-p2.0;
    let x=p1.1-p2.1;

    (y*y+x*x) as i64
}


macro_rules! get{
    ($self:ident,$a:ident)=>{
        ($self.route[$a-1],$self.route[$a])
    };
}
macro_rules! dist{
    ($self:ident;$($a:ident,$b:ident);*)=>{
        0$(+$self.dist[$a][$b])*
    }
}


pub struct In{
    pos:[(usize,usize);N]
}
impl In{
    #[inline]
    fn input()->In{
        input!{
            n:usize,
            m:usize,
            tp:[(usize,usize);N]
        }
        assert_eq!((n,m),(N,M));

        let mut it=tp.into_iter();
        In{pos:[();N].map(|_|it.next().unwrap())}
    }
}


// ステーションの大体の位置を求める
mod solver1{
    use super::*;

    struct Out{
        m:[(usize,usize);M],
        dist:[[i64;N];N],
        cnt:[usize;N+M],
        route:Vec<usize>,
        log:Vec<(bool,usize)> // type,idx
    }
    impl Out{
        #[inline]
        fn new(input:&In)->Out{
            let mut route=(0..N).collect::<Vec<_>>();
            route.push(0);
            rnd::shuffle(&mut route[1..N]);
    
            let mut cnt=[0;N+M];
            cnt[0]=2;
            cnt[1..N].fill(1);
            cnt[N..N+M].fill(usize::MAX>>1);
            let m=[();M].map(|_|(rnd::next()%1001,rnd::next()%1001));
    
            let mut dist=[[i64::MAX>>2;N];N];
            for i in 0..N{
                for j in 0..N{
                    dist[i][j]=A*A*get_dist(input.pos[i],input.pos[j]);
                }
            }
            for k in 0..N{
                for i in 0..N{
                    for j in 0..N{
                        dist[i][j]=dist[i][j].min(dist[i][k]+dist[k][j]);
                    }
                }
            }
    
            Out{m,dist,cnt,route,log:vec![]}
        }

        #[inline]
        fn reset(&mut self){
            self.route=(0..N).collect::<Vec<_>>();
            self.route.push(0);
            rnd::shuffle(&mut self.route[1..N]);
    
            self.cnt[0]=2;
            self.cnt[1..N].fill(1);
            self.cnt[N..N+M].fill(usize::MAX>>1);
            self.m=[();M].map(|_|(rnd::next()%1001,rnd::next()%1001));
        }
    
        #[inline]
        fn score(&self,input:&In)->i64{
            self.route.windows(2).map(|w|self.dist(input,w[0],w[1])).sum::<i64>()
        }
    
        #[inline]
        // #[track_caller]
        fn dist(&self,input:&In,a:usize,b:usize)->i64{
            if a<N && b<N{
                self.dist[a][b]
            }
            else if a>=N && b>=N{
                get_dist(self.m[a-N],self.m[b-N])
            }
            else if a>=N{
                A*get_dist(self.m[a-N],input.pos[b])
            }
            else{
                A*get_dist(self.m[b-N],input.pos[a])
            }
        }
    
        #[inline]
        fn sub(&self,input:&In,a:usize,p:(usize,usize))->i64{
            if a<N{
                get_dist(input.pos[a],p)*A
            }
            else{
                get_dist(self.m[a-N],p)
            }
        }
    
        #[inline]
        // idxは+Nされたあと
        fn change(&mut self,input:&In,add:i64,id:usize,new:(usize,usize),score:&mut i64)->bool{
            self.log.clear();
            let mut prev=self.route[0];
            let mut f=false;
            let mut at=1;
            let mut diff=0;
    
            for &v in &self.route[1..]{
                if f{
                    diff+=self.dist(input,prev,v)-self.dist(input,prev,id)-self.dist(input,id,v);
                }
    
                if v!=id{
                    let d=self.sub(input,prev,new)+self.sub(input,v,new)-self.dist(input,prev,v);
                    if 0>d{
                        diff+=d;
                        self.log.push((true,at));
                        at+=1;
                    }
                    prev=v;
                    at+=1;
                    f=false;
                }
                else{
                    self.log.push((false,at));
                    f=true;
                }
            }
    
            if add>=diff{
                *score+=diff;
                self.m[id-N]=new;
                for &(t,idx) in &self.log{
                    if t{
                        self.route.insert(idx,id);
                    }
                    else{
                        self.route.remove(idx);
                    }
                }
                true
            }
            else{
                false
            }
        }
    
        #[inline]
        fn try_opt2(&self,input:&In,a:usize,b:usize)->i64{
            let (a0,a1)=get!(self,a);
            let (b0,b1)=get!(self,b);

            self.dist(input,a0,b0)+self.dist(input,a1,b1)-self.dist(input,a0,a1)-self.dist(input,b0,b1)
        }
    
        #[inline]
        fn opt2(&mut self,mut a:usize,mut b:usize){
            if a>b{
                std::mem::swap(&mut a,&mut b);
            }
    
            self.route[a..b].reverse();
        }
    
        #[inline]
        fn try_insert(&self,input:&In,idx:usize,v:usize)->i64{
            let (v0,v1)=get!(self,idx);
    
            self.dist(input,v0,v)+self.dist(input,v,v1)-self.dist(input,v0,v1)
        }
    
        #[inline]
        fn insert(&mut self,idx:usize,v:usize){
            self.route.insert(idx,v);
            self.cnt[v]+=1;
        }
    
        #[inline]
        fn try_remove(&self,input:&In,idx:usize)->i64{
            let (v0,v1)=get!(self,idx);
            let v2=self.route[idx+1];
    
            self.dist(input,v0,v2)-self.dist(input,v0,v1)-self.dist(input,v1,v2)
        }
    
        #[inline]
        fn remove(&mut self,idx:usize){
            let v=self.route.remove(idx);
            self.cnt[v]-=1;
        }
    }
    
    
    pub fn sa(input:&In)->([(usize,usize);M],Vec<usize>){
        const TL:f64=0.88;
        let mut best=i64::MAX;
        let mut best_state=([(!0,!0);M],vec![]);
    
        let mut iter=0;
        let mut up=0;
        let mut th=[0;256];
    
        let mut cur=Out::new(input);

        const I:usize=6;

        debug!("solver1");
        for i in 0..I{
            cur.reset();
            let mut score=cur.score(input);
            let start=get_time();
            let tl=TL*(i+1) as f64/I as f64;
            let mut p=0.;
    
            loop{
                if iter&1023==0{
                    p=(get_time()-start)/(tl-start);
                    if p>=1.{break;}
        
                    const T:f64=35000.;
                    let heat=T*(1.-p);
        
                    th.fill_with(||(-heat*rnd::nextf().ln()) as i64);
                }
        
                let r=rnd::nextf();
        
                const A:f64=0.5; // 2-opt
                const B:f64=0.2; // insert
                const C:f64=0.2; // remove
                // const D:f64=0.1; // change
        
                if r<=A{
                    let a=rnd::range(1,cur.route.len()-1);
                    let mut b;
                    while{
                        b=rnd::range(1,cur.route.len()-1);
                        a-b+1<=2
                    }{}
        
                    let diff=cur.try_opt2(input,a,b);
        
                    if th[iter&255]>=diff{
                        score+=diff;
                        cur.opt2(a,b);
                        up+=1;
                    }
                }
                else if r<=A+B{
                    let idx=rnd::range(1,cur.route.len());
                    let mut v;
                    while{
                        v=rnd::next()%(N+M);
                        v==cur.route[idx-1] || v==cur.route[idx]
                    }{}
                    
                    let diff=cur.try_insert(input,idx,v);
                    
                    if th[iter&255]>=diff{
                        score+=diff;
                        cur.insert(idx,v);
                        up+=1;
                    }
                }
                else if r<=A+B+C && cur.route.len()!=N+1{
                    let mut idx;
                    while{
                        idx=rnd::range(1,cur.route.len()-1);
        
                        let v=cur.route[idx];
                        cur.cnt[v]==1
                    }{}
        
                    let diff=cur.try_remove(input,idx);
        
                    if th[iter&255]>=diff{
                        score+=diff;
                        cur.remove(idx);
                        up+=1;
                    }
                }
                else{
                    const S:f64=300.;
                    const T:f64=10.;
        
                    let r=(S+(T-S)*p) as i64;
                    let id=rnd::next()&7;
                    let p=cur.m[id];
                    let mut np;
                    while{
                        np=(p.0+rnd::rangei(-r,r+1) as usize,p.1+rnd::rangei(-r,r+1) as usize);
                        np.0>1000 || np.1>1000 || np==p
                    }{}
        
                    if cur.change(input,th[iter&255],id+N,np,&mut score){
                        up+=1;
                    }
                }
                iter+=1;
        
                if best>score{
                    best=score;
                    best_state=(cur.m,cur.route.clone());
                }
            }
            debug!(i,score);
        }
    
        let p=up as f64/iter as f64;
        debug!(iter,p);
        debug!(best);
        debug!(best_state.1.len());
        debug!();
    
        best_state
    }
}


// 得られたステーションから経路を求める
mod solver2{
    use super::*;

    struct Out{
        next:[[usize;N+M];N+M],
        dist:[[i64;N];N],
        route:[usize;N+1]
    }
    impl Out{
        #[inline]
        fn new(input:&In,m:&[(usize,usize);M],route:[usize;N+1])->Out{
            let mut dist_sub=[[i64::MAX>>2;N+M];N+M];
            let mut next=[[!0;N+M];N+M];
            for i in 0..N+M{
                let a=if i<N{input.pos[i]}else{m[i-N]};
                for j in 0..N+M{
                    let b=if j<N{input.pos[j]}else{m[j-N]};
                    dist_sub[i][j]=get_dist(a,b)*if i<N && j<N{A*A}
                    else if i>=N && j>=N{1}
                    else{A};
                    next[i][j]=j;
                }
            }
    
            for k in 0..N+M{
                for i in 0..N+M{
                    for j in 0..N+M{
                        if dist_sub[i][j]>dist_sub[i][k]+dist_sub[k][j]{
                            next[i][j]=next[i][k];
                            dist_sub[i][j]=dist_sub[i][k]+dist_sub[k][j];
                        }
                    }
                }
            }
    
            let mut dist=[[!0;N];N];
            for i in 0..N{
                for j in 0..N{
                    dist[i][j]=dist_sub[i][j];
                }
            }
    
            Out{next,dist,route}
        }
    
        #[inline]
        fn score(&self)->i64{
            self.route.windows(2).map(|w|self.dist[w[0]][w[1]]).sum::<i64>()
        }
    
        #[inline]
        fn try_opt2(&self,a:usize,b:usize)->i64{
            let (a0,a1)=get!(self,a);
            let (b0,b1)=get!(self,b);
    
            dist!(self;a0,b0;a1,b1)-dist!(self;a0,a1;b0,b1)
        }
    
        #[inline]
        fn opt2(&mut self,mut a:usize,mut b:usize){
            if a>b{
                std::mem::swap(&mut a,&mut b);
            }
    
            self.route[a..b].reverse();
        }
    
        #[inline]
        fn try_db(&self,a:usize,b:usize,c:usize,d:usize)->i64{
            // assert!(0<a && a+1<b && b+1<c && c+1<d && d<self.route.len());
            let (a0,a1)=get!(self,a);
            let (b0,b1)=get!(self,b);
            let (c0,c1)=get!(self,c);
            let (d0,d1)=get!(self,d);
    
            dist!(self;a0,c1;d0,b1;c0,a1;b0,d1)-dist!(self;a0,a1;b0,b1;c0,c1;d0,d1)
        }
    
        #[inline]
        fn db(&mut self,a:usize,b:usize,c:usize,d:usize){
            self.route[b..d].rotate_right(d-c);
            self.route[a..d].rotate_right(d-b);
        }
    
        #[inline]
        fn try_opt3(&mut self,a:usize,b:usize,c:usize,t:usize)->i64{
            // assert!(0<a && a+1<b && b+1<c && c<self.route.len());
            let (a0,a1)=get!(self,a);
            let (b0,b1)=get!(self,b);
            let (c0,c1)=get!(self,c);
            
            let old=dist!(self;a0,a1;b0,b1;c0,c1);
            if t==0{
                dist!(self;a0,b0;a1,c0;b1,c1)-old
            }
            else if t==1{
                dist!(self;a0,c0;b1,a1;b0,c1)-old
            }
            else if t==2{
                dist!(self;a0,b1;c0,b0;a1,c1)-old
            }
            else{
                dist!(self;a0,b1;c0,a1;b0,c1)-old
            }
        }
    
        #[inline]
        fn opt3(&mut self,a:usize,b:usize,c:usize,t:usize){
            if t&1==0{
                self.route[a..b].reverse();
            }
            if t<=1{
                self.route[b..c].reverse();
            }
            if t!=0{
                self.route[a..c].rotate_right(c-b);
            }
        }

        #[inline]
        fn build(&self)->Vec<usize>{
            let mut ret=vec![0];
            for w in self.route.windows(2){
                let mut s=w[0];
                let t=w[1];

                while s!=t{
                    s=self.next[s][t];
                    ret.push(s);
                }
            }
            ret
        }
    }

    
    pub fn sa(input:&In,m:&[(usize,usize);M],route:Vec<usize>)->Vec<usize>{
        let mut cur={
            let mut seen=[true;N+M];
            let mut it=route.into_iter().filter(|&x|{
                let f=seen[x];
                seen[x]=false;
                x<N && f
            }).chain(0..=0);
            Out::new(input,m,[0;N+1].map(|_|it.next().unwrap()))
        };

        let mut score=cur.score();
        debug!("solver2");
        debug!(score);
        let mut best=score;
        let mut best_state=cur.route;

        let mut iter=0;
        let mut up=0;
        let mut th=[0;256];

        let start=get_time();
        loop{
            if iter&1023==0{
                const TL:f64=0.98;
                let p=(get_time()-start)/(TL-start);
                if p>=1.{
                    break;
                }
    
                const T0:f64=1000000.;
                const T1:f64=0.;
    
                let heat=T0+(T1-T0)*p;
    
                th.fill_with(||(-heat*rnd::nextf().ln()) as i64);
            }
            iter+=1;
    
            const A:f64=0.8; // 2-opt
            const B:f64=0.1; // 3-opt
            // const C:f64=0.1; // double-bridge
            let r=rnd::nextf();
            
            if r<=A{
                let a=rnd::range(1,cur.route.len());
                let mut b;
                while{
                    b=rnd::range(1,cur.route.len());
                    a-b+1<=2
                }{}
        
                let diff=cur.try_opt2(a,b);
                
                if th[iter&255]>=diff{
                    cur.opt2(a,b);
                    score+=diff;
                    up+=1;
                }
            }
            else{
                let mut x=[rnd::range(1,cur.route.len()),!0,!0,!0];
                while{
                    x[1]=rnd::range(1,cur.route.len());
                    x[0]-x[1]+1<=2
                }{}
                while{
                    x[2]=rnd::range(1,cur.route.len());
                    x[0]-x[2]+1<=2 || x[1]-x[2]+1<=2
                }{}
    
                if r<=A+B{
                    x[..3].sort_unstable();
                    let t=rnd::next()&3;
                    let diff=cur.try_opt3(x[0],x[1],x[2],t);
    
                    if th[iter&255]>=diff{
                        cur.opt3(x[0],x[1],x[2],t);
                        score+=diff;
                        up+=1;
                    }
                } 
                else{
                    while{
                        x[3]=rnd::range(1,cur.route.len());
                        x[0]-x[3]+1<=2 || x[1]-x[3]+1<=2 || x[2]-x[3]+1<=2
                    }{}
                    x.sort_unstable();
                    let diff=cur.try_db(x[0],x[1],x[2],x[3]);
        
                    if th[iter&255]>=diff{
                        cur.db(x[0],x[1],x[2],x[3]);
                        score+=diff;
                        up+=1;
                    }
                }
            }
    
            if best>score{
                best=score;
                best_state=cur.route;
            }
        }
    
        let p=up as f64/iter as f64;
        debug!(iter,p);
        debug!(score,best);
        debug!();

        std::mem::swap(&mut best_state,&mut cur.route);
    
        cur.build()
    }
}


// 得られた経路からステーションの位置を微調整
mod solver3{
    use super::*;
    const DY:[usize;8]=[1,0,!0,0,1,1,!0,!0];
    const DX:[usize;8]=[0,1,0,!0,1,!0,1,!0];

    // 重複しているやつのinitをうまくやること！
    struct Out{
        m:[(usize,usize);M],
        path:[Vec<usize>;M]
    }
    impl Out{
        #[inline]
        fn new(m:[(usize,usize);M],route:&[usize])->Out{
            let mut path=[();M].map(|_|vec![]);
            for w in route.windows(2){
                if N <=w[0]{
                    path[w[0]-N].push(w[1]);
                }
                if N <=w[1]{
                    path[w[1]-N].push(w[0]);
                }
            }

            Out{m,path}
        }
        
        #[inline]
        fn score(&self,input:&In)->i64{
            let mut ret=0;
            for i in 0..M{
                for &j in self.path[i].iter(){
                    if j<=i+N{
                        ret+=self.dist(input,j,self.m[i]);
                    }
                }
            }
            ret
        }

        #[inline]
        fn dist(&self,input:&In,a:usize,p:(usize,usize))->i64{
            if a<N{
                A*get_dist(input.pos[a],p)
            }
            else{
                get_dist(self.m[a-N],p)
            }
        }

        #[inline]
        fn try_change(&self,input:&In,idx:usize,np:(usize,usize))->i64{
            let old=self.path[idx].iter().map(|&x|self.dist(input,x,self.m[idx])).sum::<i64>();
            let new=self.path[idx].iter().map(|&x|self.dist(input,x,np)).sum::<i64>();

            new-old
        }
    }

    pub fn hc(input:&In,m:[(usize,usize);M],route:&[usize])->[(usize,usize);M]{
        let mut cur=Out::new(m,route);
        let mut score=cur.score(input);
        
        const I:usize=100000;
        let mut up=0;
        for _ in 0..I{
            let mut tr=rnd::next();
            let idx=tr>>32&7;
            let p=cur.m[idx];
            let mut np;
            while{
                let dr=tr&7;
                np=(p.0+DY[dr],p.1+DX[dr]);
                np.0>1000 || np.1>1000
            }{tr=rnd::next();}

            let diff=cur.try_change(input,idx,np);
            if 0>=diff{
                score+=diff;
                cur.m[idx]=np;
                up+=1;
            }
        }
        assert_eq!(score,cur.score(input));
        let p=up as f64/I as f64;
        debug!(p);

        cur.m
    }
}


fn main(){
    let input=In::input();
    let (m,route)=solver1::sa(&input);
    let route=solver2::sa(&input,&m,route);
    let m=solver3::hc(&input,m,&route);

    let mut score=0;
    for w in route.windows(2){
        let s=if w[0]<N{input.pos[w[0]]}else{m[w[0]-N]};
        let t=if w[1]<N{input.pos[w[1]]}else{m[w[1]-N]};

        score+=get_dist(s,t)*if w[0]<N && w[1]<N{A*A}
        else if w[0]>=N && w[1]>=N{1}
        else{A};
    }
    debug!(score);
    println!("{}",(1000000000./(1000.+(score as f64).sqrt())).round());

    // for (a,b) in m{
    //     println!("{a} {b}");
    // }

    // println!("{}",route.len());
    // for v in route{
    //     if v<N{
    //         println!("1 {}",v+1);
    //     }
    //     else{
    //         println!("2 {}",v-N+1);
    //     }
    // }
    // debug!(get_time());
}