#include <bits/stdc++.h>
# define endl            '\n'
# define clr(x,a)        memset(x,a,sizeof(x))
# define vi              vector<int>
# define all(a)          a.begin(), a.end()
# define deb(x)          cout<<#x<<"=="<<x<<endl;
# define pb              push_back
# define sc              scanf
# define pr              printf
# define linija          cout<<"___________________________________\n";
# define st              first
# define nd              second
using namespace std;
typedef long long ll;
const int mxN=100006, mod=99978456, LOG=23;
const double maxd=14300001000, max_score=1500000000000000.0;
const ll maxd_squared=1999999996000000003;
int n,k,test,tacka[2],tin,ideovi_viskova[mxN],br_viska,visak[mxN],prazni,glob,idstaz[mxN],max_dub=5,ostatak,kolko,uradjen[mxN],cnt_grupica[20];
int h1,h2,w1,w2,dh,dw,visited[300][300],glob_visited,uzeta[mxN],grupe_runnera[20][10000],br_gr[20],ps[20],indeks_grupe[mxN],pzsq[mxN];
int niz1[mxN],niz2[mxN],br1,br2,idv,br_optimizacija,granica_dp=50,stek[120],brstek,stek2[120],brstek2;
float score,best_score,opt_score,duzine_pre[mxN],duzine[mxN],d1,d2,pd[1005],s[2];
map<int, int> mapa;  //12+23-13
clock_t vreme0;

struct slog_quea{
   float val;
   int idstaz, j, id;
   bool operator <(const slog_quea &P)const{
      return P.val>val;
   }
}qupom;
struct Solution{
   int id, x, y;
}res[mxN];
struct Runner{
   float s, ss;
   int id, x, y;
//   int poredak;
}r[mxN], r2[mxN];
struct Point{
   int x, y, id, idrunera;
}bc[mxN];
struct pagru{
   vi v; //idevi tacaka koje sam obisao
   float duzina;
   int idrunnera, pocx, pocy;
}staze[mxN];
struct Dinamika{
   int prev, iksd, t, sta_je_izmedju;   //izkogsamdosa
   float score;
   void ispis(int x){
      cout<<"za: "<<x<<" -> ";
      cout<<"score=="<<score<<", prev=="<<prev<<endl;
   }
}dp[2][mxN], trenic, bestic;
bool cmp_res_id(Solution a, Solution b){return a.id<b.id;}
bool cmp_r_id(Runner a, Runner b){return a.id<b.id;}
bool cmp_r_opadajuce(Runner a, Runner b){return a.s>b.s;}
bool cmp_r_rastuce(Runner a, Runner b){return a.s<b.s;}
bool cmp_bc_id(Point a, Point b){return a.id<b.id;}
bool cmp_bc_x(Point a, Point b){return a.x<b.x;}
bool cmp_bc_y(Point a, Point b){return a.y<b.y;}
bool cmp_staze_opadajuce(pagru a, pagru b){return a.duzina>b.duzina;}
bool cmp_staze_rastuce(pagru a, pagru b){return a.duzina<b.duzina;}
bool cmp_float_opadajuce(float x, float y) {return x>y;}
bool cmp_float_rastuce(float x, float y) {return x<y;}
priority_queue<slog_quea> q;
void svi1(){
   for(int i=1; i<=k; i++){
      r[i].x=bc[i].x;
      r[i].y=bc[i].y;
      bc[i].idrunera=i;
   }
   for(int i=k+1; i<=n; i++) bc[i].idrunera=1;
}
float dist(ll x1, ll y1, ll x2, ll y2){
   ll ry=(y1-y2), rx=(x1-x2);
   return sqrt(rx*rx+ry*ry);
}
void swapuj_x_y(){
   for(int i=1; i<=n; i++) swap(bc[i].x, bc[i].y);
}
void calcscore(){    ///ovo sranje menjaa r-oveeeeeeeee !!!!!!!! fadsds gdf f
   score=0;
   sort(r+1, r+1+k, cmp_r_id);
   for(int i=1; i<=k; i++){
      r[i].x=res[i].x;
      r[i].y=res[i].y;
   }
   sort(bc+1, bc+1+n, cmp_bc_id);
   for(int i=1; i<=n; i++){
      score+=dist(r[bc[i].idrunera].x, r[bc[i].idrunera].y, bc[i].x, bc[i].y)*r[bc[i].idrunera].s;
      r[bc[i].idrunera].x=bc[i].x;
      r[bc[i].idrunera].y=bc[i].y;
   }
}
void unos(){
   if(tin==1) freopen("input_t1.in", "r", stdin);
   else if(tin==2) freopen("input_t2.in", "r", stdin);
   else if(tin==3) freopen("input_t3.in", "r", stdin);
   else if(tin==4) freopen("input_t4.in", "r", stdin);
   else if(tin==5) freopen("input_t5.in", "r", stdin);
   else if(tin==6) freopen("testic.in", "r", stdin);
   else freopen("runners.in", "r", stdin);

   sc("%d%d", &n, &k);
   if(k<=10) test=1;
   else if(k<=100) test=2;
   else if(k<=1000) test=3;
   else if(k<=10000) test=4;
   else test=5;

   for(int i=1; i<=k; i++){
      sc("%f", &r[i].s);
      r[i].id=i;
      r[i].ss=r[i].s*r[i].s;
      r[i].x=r[i].y=1;
      res[i].id=i;
      res[i].x=res[i].y=1;
   }

   h1=w1=1e9; h2=w2=0;
   for(int i=1; i<=n; i++){
      sc("%d %d", &bc[i].x, &bc[i].y);
      bc[i].id=i;
      bc[i].idrunera=1;
      h1=min(h1, bc[i].y);
      h2=max(h2, bc[i].y);
      w1=min(w1, bc[i].x);
      w2=max(w2, bc[i].x);
   }
//   swapuj_x_y();
//   for(int i=1; i<=n; i++){
//
//   }
   dw=w2-w1+1; dh=h2-h1+1;
}
void ispis(){
   sort(res+1, res+1+k, cmp_res_id);
   sort(bc+1, bc+1+n, cmp_bc_id);
   freopen("runners.out", "w", stdout);
   for(int i=1; i<=k; i++) pr("%d %d\n", res[i].x, res[i].y);
   for(int i=1; i<=n; i++){
      pr("%d\n", bc[i].idrunera);
   }
//   calcscore();
//   deb(score)
}
void ispisi_staze(){
   cout<<"staze\n";
   for(int i=1; i<=k; i++){
      cout<<i<<" duzina=="<<staze[i].duzina<<" -> ";
      for(int j: staze[i].v) cout<<j<<" ";
      cout<<endl;
   }
   cout<<endl;
}
ll dist_squared(int p1[2], int p2[2]){
   ll dx=(p1[0]-p2[0]), dy=(p1[1]-p2[1]);
   return dx*dx+dy*dy;
}
int duzina_cifara(float x){
   int ret=0;
   while(x>1){
      ret++;
      x/=10;
   }
   return ret;
}
void calc_opt_score(){ //racuna_opt_score O(k), radi sa duzine[]
   opt_score=0;
   for(int i=1; i<=k; i++) opt_score+=r[i].s*duzine[i];
}
void update_s1(int p1, int p2, int p3){   //racuna d1 O(sqrt)
   if(p1==-1){
      if(p3==-1) d1=0;
      else d1=-dist(bc[p2].x, bc[p2].y, bc[p3].x, bc[p3].y);
   }
   else{
      if(p3==-1) d1=-dist(bc[p2].x, bc[p2].y, bc[p1].x, bc[p1].y);
      else d1=dist(bc[p1].x, bc[p1].y, bc[p3].x, bc[p3].y) //dist1
              -dist(bc[p2].x, bc[p2].y, bc[p1].x, bc[p1].y) //dist2
              -dist(bc[p2].x, bc[p2].y, bc[p3].x, bc[p3].y);  //dist3
   }
}
void update_s2(int pret, int p, int s2){  //racuna d2 O(sqrt) -- N al se to neutralise  //ne radi za sada (treba ubaciti prethodni)
   int sajz2=staze[s2].v.size();
//   cout<<"updatujem s2\n";

   if(idv==sajz2){  //pucam ga na kraj
      if(pret==-1) d2=dist(bc[staze[s2].v[sajz2-1]].x, bc[staze[s2].v[sajz2-1]].y, bc[p].x, bc[p].y);
      else d2=dist(bc[pret].x, bc[pret].y, bc[p].x, bc[p].y);
      return;
   }
   while(staze[s2].v[idv]<p){ //trazim prvog veceg, ide PRE idv-a
      idv++;
//      cout<<"idv raste\n";
      pret=-1;
      if(idv==sajz2){
         d2=dist(bc[staze[s2].v[sajz2-1]].x, bc[staze[s2].v[sajz2-1]].y, bc[p].x, bc[p].y);
         return;
      }
   }
//   deb(pret);
//   deb(idv);
   if(idv==0){
      if(pret==-1){
         d2=dist(bc[staze[s2].v[idv]].x, bc[staze[s2].v[idv]].y, bc[p].x, bc[p].y);
      }
      else{
         d2=dist(bc[staze[s2].v[idv]].x, bc[staze[s2].v[idv]].y, bc[p].x, bc[p].y);
      }
      return;
   }
   //izmedju idv
   if(pret==-1){
      d2=dist(bc[staze[s2].v[idv]].x, bc[staze[s2].v[idv]].y, bc[p].x, bc[p].y)
         +dist(bc[staze[s2].v[idv-1]].x, bc[staze[s2].v[idv-1]].y, bc[p].x, bc[p].y)
         -dist(bc[staze[s2].v[idv-1]].x, bc[staze[s2].v[idv-1]].y, bc[staze[s2].v[idv]].x, bc[staze[s2].v[idv]].y);
   }
   else{
//      cout<<"else \n";
      d2=dist(bc[staze[s2].v[idv]].x, bc[staze[s2].v[idv]].y, bc[p].x, bc[p].y)
         +dist(bc[pret].x, bc[pret].y, bc[p].x, bc[p].y)
         -dist(bc[pret].x, bc[pret].y, bc[staze[s2].v[idv]].x, bc[staze[s2].v[idv]].y);
   }
}
void konacna_raspodela(){
   sort(r+1, r+1+k, cmp_r_opadajuce);
   sort(staze+1, staze+1+k, cmp_staze_rastuce);   //moze ovo ne treba ovde, mislim sigurno ne treba
//   cout<<"Konacna raspodela\n";
//   for(int i=1; i<=k; i++)
//      cout<<staze[i].duzina<<endl;
   for(int i=1; i<=k; i++){
      if(staze[i].v.size()){
//         cout<<i<<endl;
         res[r[i].id].x=bc[staze[i].v[0]].x;
         res[r[i].id].y=bc[staze[i].v[0]].y;
      }
      else{ //ne koristim ga
         res[r[i].id].x=1;
         res[r[i].id].y=1;
      }
      for(int j: staze[i].v) bc[j].idrunera=r[i].id;
   }
}
void izracunaj_score_pre(){
   for(int i=1; i<=k; i++) duzine[i]=staze[i].duzina;
   sort(duzine+1, duzine+1+k, cmp_float_rastuce);
   calc_opt_score();
   score=opt_score;
}
void sredi_duzine(float dis1, float dis2){   //aj kao radi, mislim dobro ga sortira
//   cout<<"sredjujem duzine\n";
   for(int i=1; i<=k-2; i++) duzine[i]=duzine_pre[i];
   duzine[k-1]=dis1;
//   cout<<"duzine pre: ";
//   for(int i=1; i<=k-2; i++) cout<<duzine[i]<<" ";
//   cout<<endl;
   int br=k-1;
   while(duzine[br]<duzine[br-1]){
      swap(duzine[br], duzine[br-1]);
      br--;
   }
   br=k;
   duzine[k]=dis2;
   while(duzine[br]<duzine[br-1]){
      swap(duzine[br], duzine[br-1]);
      br--;
   }
//   cout<<"duzine posle: ";
//   for(int i=1; i<=k; i++) cout<<duzine[i]<<" ";
//   cout<<endl;
//   cout<<endl;
}
void optimizacija(int s1, int s2){     //trebalo biii nesto kao O(N*(K+nesto)+nesto)
   if(k<s2 || staze[s1].v.size()<=1 || staze[s2].v.size()==0) return;
//   cout<<"optimizacija\n";
//   cout<<s1<<" "<<s2<<endl;
   int pret1=-1, pret2=-1, sajz2=staze[s2].v.size(), sajz1=staze[s1].v.size(), brojac_duzina=0;
   br1=br2=idv=0;
   izracunaj_score_pre();  //imam ga u score-u
//   cout<<"Pocetni score=="<<score<<endl;
   for(int i: staze[s2].v) niz2[++br2]=i; //svi iz s2 idu u niz2
   for(int i=1; i<=k; i++){   //racuna sve osim s1 i s2
      if(i!=s1 && i!=s2)
         duzine_pre[++brojac_duzina]=staze[i].duzina;
   }
   sort(duzine_pre+1, duzine_pre+1+k-2);   //trebalo bi da je brojac_duzina=k-2
   for(int j=0; j<sajz1; j++){   //j-tu prebacujem u stazu[s2]
      if(j==sajz1-1){
         if(pret1==-1) update_s1(-1, staze[s1].v[j], -1);
         else update_s1(pret1, staze[s1].v[j], -1);
      }
      else{
         if(pret1==-1) update_s1(-1, staze[s1].v[j], staze[s1].v[j+1]);
         else update_s1(pret1, staze[s1].v[j], staze[s1].v[j+1]);
      }
      update_s2(pret2, staze[s1].v[j], s2);   //valjda update-ovi rade... kada updateujem SCORE, updatujem pret
//      cout<<"\nnova duzina za s1: "<<staze[s1].duzina+d1<<endl;
//      cout<<"nova duzina za s2: "<<staze[s2].duzina+d2<<endl;

      sredi_duzine(staze[s1].duzina+d1, staze[s2].duzina+d2);
      calc_opt_score();
//      deb(opt_score);
      if(opt_score<score){ //prebacujem j u s2, ovde updatujem pret
//         cout<<"opt score < score\n";
         br_optimizacija++;
         niz2[++br2]=staze[s1].v[j];
         pret2=staze[s1].v[j];
         staze[s1].duzina+=d1;
         staze[s2].duzina+=d2;
         score=opt_score;
//         deb(score);
      }
      else{
         pret1=staze[s1].v[j];
         niz1[++br1]=staze[s1].v[j];
         pret2=-1;
      }
//      linija;
   }

   sort(niz1+1, niz1+1+br1);
   sort(niz2+1, niz2+1+br2);
   staze[s1].v.clear();
   staze[s2].v.clear();
   for(int i=1; i<=br1; i++)
      staze[s1].v.pb(niz1[i]);
   for(int i=1; i<=br2; i++)
      staze[s2].v.pb(niz2[i]);
//   cout<<"na kraju score=="<<score<<endl<<endl;
}
void poredjaj_redom(){
   for(int i=1; i<=k; i++){
      bc[i].idrunera=i;
      r[i].x=bc[i].x;
      r[i].y=bc[i].y;

      res[i].x=bc[i].x;
      res[i].y=bc[i].y;
      staze[i].v.clear();
      staze[i].v.pb(i);
      staze[i].duzina=0;
   }
}
void poredjaj_kakasto(){
   int koren=sqrt(k), xw, xh, th, tw, idx, br=0;
   xw=dw/koren+(dw%koren!=0);
   xh=dh/koren+(dh%koren!=0);
//   cout<<dw/xw<<endl;
//   cout<<dh/xh<<endl;
   int maxth=dh/xh+1, maxtw=dw/xw+1;
   maxth=maxtw=0;
   for(int i=1; i<=n; i++){
      th=(bc[i].y-h1)/xh+1;
      tw=(bc[i].x-w1)/xw+1;
      idx=tw+(th-1)*koren;
      maxth=max(th, maxth);
      maxtw=max(tw, maxtw);
      if(th<=1 || tw<=1 || tw>=(maxtw) || th>=(maxth)) continue;
      if(indeks_grupe[idx]==2) continue;

      br++;
      indeks_grupe[br]=1;

      r[br].x=bc[i].x;
      r[br].y=bc[i].y;

      staze[br].v.clear();
      staze[br].v.pb(i);
      staze[br].duzina=0;
      if(br==k) break;

   }
//   deb(br);
//   deb(k);
//   exit(k-br);

//   for(int i=1; i<=n; i++){
//      if(indeks_grupe[i]) continue;
//      if(br==k) return;
//      br++;
//      indeks_grupe[i]=1;
//
//      r[i].x=bc[i].x;
//      r[i].y=bc[i].y;
//
//      staze[i].v.clear();
//      staze[i].v.pb(i);
//      staze[i].duzina=0;
//   }
}
void algoritam_najblizi_put_bez_staza_samo_najblizi(){
//   cout<<"najblizi put_bez_staza_samo_najblizi\n";
   poredjaj_redom();
//   poredjaj_kakasto();
   float najblizi, tren;
   ll najbl_ll;
   int t1[2], t2[2], mojid;
   for(int i=k+1; i<=n; i++){
      if(indeks_grupe[i]) continue;
      najblizi=100.0*maxd_squared;
      t1[0]=bc[i].x; t1[1]=bc[i].y;
      for(int j=1; j<=k; j++){
         if(staze[j].v.size()==0) continue;
//         if(staze[j].v[staze[j].v.size()-1]>i) continue;
         t2[0]=r[j].x; t2[1]=r[j].y;
         tren=r[j].ss*dist_squared(t1, t2);

         if(tren<najblizi){
            najblizi=tren;
            najbl_ll=dist_squared(t1, t2);
            mojid=j;
         }
      }
      bc[i].idrunera=mojid;
      r[mojid].x=bc[i].x;
      r[mojid].y=bc[i].y;

      staze[mojid].v.pb(i);
      staze[mojid].duzina+=sqrt(najbl_ll);
   }
   sort(staze+1, staze+1+k, cmp_staze_rastuce);   //moze ovo ne treba ovde, mislim sigurno ne treba
   sort(r+1, r+1+k, cmp_r_opadajuce);   //moze ovo ne treba ovde, mislim sigurno ne treba

   for(int i=1; i<k; i++) optimizacija(i, k);

   if(k<=100){
//      cout<<"OPtimizuje\n";
      for(int i=1; i<k; i++){
         br_optimizacija=0;
         optimizacija(i, k);
         if(br_optimizacija){
            brstek++;
            stek[brstek]=i;
         }
      }
      while(brstek>0){
         if(clock()-vreme0>2500) break;
         brstek2=0;
         for(int i=1; i<=brstek; i++){
            br_optimizacija=0;
            optimizacija(stek[i], k);
            if(br_optimizacija){
               brstek2++;
               stek2[brstek2]=stek[i];
            }
         }
         for(int i=1; i<=brstek2; i++) stek[i]=stek2[i];
         brstek=brstek2;
      }
   }
   for(int i=1; i<=k/2; i++) optimizacija(i, k-i+1);
   konacna_raspodela();
}
void pocetak_staza(){
   for(int i=1; i<=k; i++){
      staze[i].pocx=res[i].x;
      staze[i].pocy=res[i].y;
      staze[i].duzina=0;
      staze[i].v.clear();
      staze[i].v.pb(i);
   }
}
void algoritam_najblizi_put(){
//   cout<<"algoritam najblizi put\n";
   pocetak_staza();
   ll najblizi, tren;
   int t1[2], t2[2], mojid, pret;
   for(int i=k+1; i<=n; i++){
      najblizi=maxd_squared;
      t1[0]=bc[i].x; t1[1]=bc[i].y;
      for(int j=1; j<=min(k, 1000); j++){
         pret=staze[j].v[staze[j].v.size()-1];
         t2[0]=bc[pret].x; t2[1]=bc[pret].y;
         tren=dist_squared(t1, t2);
         if(tren<najblizi){
            najblizi=tren;
            mojid=j;
         }
      }
      staze[mojid].duzina+=sqrt(najblizi);
      staze[mojid].v.pb(i);
   }
   //konacna raspodela
   sort(staze+1, staze+1+k, cmp_staze_rastuce);   //moze ovo ne treba ovde, mislim sigurno ne treba
   sort(r+1, r+1+k, cmp_r_opadajuce);   //moze ovo ne treba ovde, mislim sigurno ne treba
   int kraj=50;
   if(k<=10){
      kraj=100;
   }
   for(int i=1; i<=kraj; i++){
      for(int j=1; j<k; j++){
         optimizacija(j, k);
      }
   }
//   deb(score);
   konacna_raspodela();
//   for(int i=1; i<=k; i++){
//      cout<<"staza "<<i<<" duzina: "<<staze[i].duzina<<endl;
//   }
//   deb(br_optimizacija);
cout<<staze[1].duzina<<endl<<staze[2].duzina<<endl;
}
float dist_triple(int i, int ret){
   int t1[2], t2[2];
   if(ret==0){
      t1[0]=bc[staze[i].v[ret]].x; t1[1]=bc[staze[i].v[ret]].y;
      t2[0]=bc[staze[i].v[ret+1]].x; t2[1]=bc[staze[i].v[ret+1]].y;
      return dist(t1[0], t1[1], t2[0], t2[1]);
   }
   if(ret==staze[i].v.size()-1){
      t1[0]=bc[staze[i].v[ret]].x; t1[1]=bc[staze[i].v[ret]].y;
      t2[0]=bc[staze[i].v[ret-1]].x; t2[1]=bc[staze[i].v[ret-1]].y;
      return dist(t1[0], t1[1], t2[0], t2[1]);
   }
   float retic=0;
   t1[0]=bc[staze[i].v[ret-1]].x; t1[1]=bc[staze[i].v[ret-1]].y;
   t2[0]=bc[staze[i].v[ret+1]].x; t2[1]=bc[staze[i].v[ret+1]].y;
   retic=-dist(t1[0], t1[1], t2[0], t2[1]);

   t1[0]=bc[staze[i].v[ret]].x; t1[1]=bc[staze[i].v[ret]].y;
   retic+=dist(t1[0], t1[1], t2[0], t2[1]);

   t2[0]=bc[staze[i].v[ret-1]].x; t2[1]=bc[staze[i].v[ret-1]].y;
   retic+=dist(t1[0], t1[1], t2[0], t2[1]);
   return retic;
}
void update_duzine(int i, int ret){
   staze[i].duzina-=dist_triple(i, ret);
}
int precalc_stazu(int i){
   if(staze[i].v.size()<=2) return -1;
//   cout<<"precalcam stazu\n";
   int ret=-1;
   ll maxval=0, trenval;
   int t1[2], t2[2];
   for(int j=1; j<staze[i].v.size()-1; j++){   //uklanjam j-tog
      t1[0]=bc[staze[i].v[j-1]].x; t1[1]=bc[staze[i].v[j-1]].y;
      t2[0]=bc[staze[i].v[j]].x; t2[1]=bc[staze[i].v[j]].y;
      trenval=dist_squared(t1, t2);   //+ d(j, j-1)
      t1[0]=bc[staze[i].v[j+1]].x; t1[1]=bc[staze[i].v[j+1]].y;
      trenval+=dist_squared(t1, t2);   //+ d(j, j+1)
      t2[0]=bc[staze[i].v[j-1]].x; t2[1]=bc[staze[i].v[j-1]].y;
      trenval-=dist_squared(t1, t2);   //- d(j+1, j-1)

      if(trenval>maxval){
         maxval=trenval;
         ret=j;
      }
   }
   if(ret!=-1) update_duzine(i, ret);
   return ret;
}
void update_queue(int idstaz){
   qupom.idstaz=idstaz;
   pzsq[idstaz]++;
//   if(pzsq[idstaz]==2) cout<<"yewtew\n";
   for(int j=0; j<staze[idstaz].v.size(); j++){
      qupom.j=j;
      qupom.val=dist_triple(idstaz, j);
      qupom.id=pzsq[idstaz];
      q.push(qupom);
   }
}
void skidanje(){
//   for(int i=1; i<=k; i++) pzsq[i]=1Z;
//   cout<<"pocelo skidanje\n";
   for(int i=1; i<=k; i++){
      if(staze[i].v.size()>=2) update_queue(i);
   }
   prazni=br_viska=0;
   for(int i=1; i<=k; i++)
      if(staze[i].v.size()==0) prazni++;

//   int raz=0;
//   while(q.size()){
//      if(q.top().j>=staze[q.top().idstaz].v.size()) raz++;
////      pr("%d\n", q.top().id);
//      q.pop();
//   }
//   deb(raz);

//   exit(100);

   while(prazni>0 && q.size()){
      qupom=q.top();
      q.pop();
      if(pzsq[qupom.idstaz]!=qupom.id) continue;
      prazni--;
      ideovi_viskova[++br_viska]=staze[qupom.idstaz].v[qupom.j];

      staze[qupom.idstaz].v.erase(staze[qupom.idstaz].v.begin()+qupom.j);
      staze[qupom.idstaz].duzina-=qupom.val;

      if(staze[qupom.idstaz].v.size()>=2) update_queue(qupom.idstaz);
      else pzsq[qupom.idstaz]++;
   }
   deb(br_viska);
   deb(prazni);
}
void delovi_koordinatnog_sistema(){ //dusko me izjebo
   if(dw<k){  //ovo ne bi trebalo nikad da se desi
      svi1();
      return;
   }
   int koren=sqrt(k), th, tw, idx, pret, xw, xh, moj_najblizi;

   xw=dw/koren+(dw%koren!=0);
   xh=dh/koren+(dh%koren!=0);

   float d1, d2;
   for(int i=1; i<=n; i++){   //samOO pravljenje stazi
      visak[i]=i;
      th=(bc[i].y-h1)/xh+1;
      tw=(bc[i].x-w1)/xw+1;

      idx=tw+(th-1)*koren;
      if(staze[idx].v.size()!=0){
         pret=staze[idx].v[staze[idx].v.size()-1];
         d1=dist(bc[i].x, bc[i].y, bc[pret].x, bc[pret].y);
         staze[idx].duzina+=d1;
      }
      staze[idx].v.pb(i);
   }

   int nviska=n, fjaval, idstaz, pocetakrunera=1, trenid=1;

   skidanje();
   //konacna raspodela
   sort(r+1, r+1+k, cmp_r_rastuce);
   sort(staze+1, staze+1+k, cmp_staze_opadajuce);
//   for(int i=1; i<=k; i++){
//      mapa[duzina_cifara(staze[i].duzina)];
//   }
//   for(int i=2; i<=12; i++) cout<<mapa[i]<<endl;
   nviska=1;
   int granica=0;
   for(int i=1; i<=k; i++){
      if(staze[i].v.size()){
         if(staze[i].v.size()>1) granica++;
         res[r[nviska].id].x=bc[staze[i].v[0]].x;
         res[r[nviska].id].y=bc[staze[i].v[0]].y;
         for(int j: staze[i].v)
            bc[j].idrunera=r[nviska].id;
         nviska++;
      }
   }

   for(int i=nviska, j=1; j<=br_viska; i++, j++){
      res[r[i].id].x=bc[ideovi_viskova[j]].x;
      res[r[i].id].y=bc[ideovi_viskova[j]].y;
      bc[ideovi_viskova[j]].idrunera=r[i].id;
   }
}
void rekurzivno(int poc, int kraj, int dub, int id_gr){ //[poc, kraj]
   if(dub&1) sort(bc+poc, bc+1+kraj, cmp_bc_x); //x
   else sort(bc+poc, bc+1+kraj, cmp_bc_y);   //y
   if(dub==max_dub){ //sklapanje
      for(int i=poc; i<=kraj; i++)
         indeks_grupe[bc[i].id]=id_gr;
      return;
   }
   rekurzivno(poc, (poc+kraj)/2, dub+1, id_gr);
   rekurzivno( (poc+kraj)/2+1, kraj, dub+1, id_gr+(1<<(max_dub-dub-1)) );
}
void izracunaj_cnt_grupice(){
   int delovi=(1<<(max_dub-1));
   for(int i=0; i<delovi; i++){
      if(i<ostatak) cnt_grupica[i]=kolko+1;
      else cnt_grupica[i]=kolko;

      if(i==0) ps[i]=cnt_grupica[i];
      else ps[i]=ps[i-1]+cnt_grupica[i];
      br_gr[i]=0;
   }
}
void sortiraj_r(){
   int idr=1, delovi=(1<<(max_dub-1));
   sort(r+1, r+1+k, cmp_r_rastuce);
   for(int i=0; i<delovi; i++){
      for(int j=i+1; j<=k; j+=delovi){
         r2[idr]=r[j];
         idr++;
      }
   }
   for(int i=1; i<=n; i++) r[i]=r2[i];
}
void namesti_pocetne_koordinate(){
   int idr=0, id_gr, maxid=0;
   for(int i=1; i<=n; i++){
      id_gr=indeks_grupe[i];
      maxid=max(maxid, id_gr);
//      cout<<i<<" ("<<bc[i].x<<", "<<bc[i].y<<") idgr: "<<id_gr;
      if(cnt_grupica[id_gr]==br_gr[id_gr]) continue;
//      deb(id_gr);
      br_gr[id_gr]++;
      if(id_gr==0) idr=br_gr[id_gr];
      else idr=ps[id_gr-1]+br_gr[id_gr];
      uradjen[i]=idr;

      r[idr].x=bc[i].x;
      r[idr].y=bc[i].y;

      res[r[idr].id].x=r[idr].x;
      res[r[idr].id].y=r[idr].y;

      grupe_runnera[id_gr][br_gr[id_gr]]=idr;
   }
//   deb(maxid);
}
void pripremi_staze(){
   int idr=0, id_gr;
   for(int i=1; i<=n; i++){
      id_gr=indeks_grupe[i];
//      cout<<i<<" ("<<bc[i].x<<", "<<bc[i].y<<") idgr: "<<id_gr;
      if(cnt_grupica[id_gr]==br_gr[id_gr]){
//         cout<<"\n";
         continue;
      }
//      cout<<" -> uzeo sam je ";
      idr++;
      br_gr[id_gr]++;
      uradjen[i]=idr;
//      deb(idr);
      r[idr].x=bc[i].x;
      r[idr].y=bc[i].y;

      staze[idr].pocx=r[idr].x;
      staze[idr].pocy=r[idr].y;
      staze[idr].duzina=0;
      staze[idr].v.clear();
      staze[idr].v.pb(i);

      grupe_runnera[id_gr][br_gr[id_gr]]=idr;
   }
}
void trazenje_najbrzeg_runera(){
   float najblizi, tren;
//   for(int i=0; i<8; i++){
//      cout<<"grupa "<<i<<" :\n";
//      for(int j=1; j<=br_gr[i]; j++)
//         cout<<grupe_runnera[i][j]<<" ";
//      cout<<endl;
//   }
   int mojid, id_gr, t1[2], t2[2], idr;
   for(int i=1; i<=n; i++){
      if(uradjen[bc[i].id]) mojid=uradjen[bc[i].id];
      else{
         id_gr=indeks_grupe[bc[i].id];
//         deb(id_gr);
         najblizi=100.0*maxd_squared;
         t1[0]=bc[i].x; t1[1]=bc[i].y;

         for(int j=1; j<=br_gr[id_gr]; j++){
            idr=grupe_runnera[id_gr][j];
            t2[0]=r[idr].x; t2[1]=r[idr].y;
            tren=r[idr].ss*dist_squared(t1, t2);

            if(tren<najblizi){
               najblizi=tren;
               mojid=idr;
            }
         }
      }
//      bc[i].idrunera=r[mojid].id;
//      deb(mojid);
      if(staze[mojid].v.size()>=1){
         idr=staze[mojid].v[staze[mojid].v.size()-1];
         staze[mojid].duzina+=dist(bc[i].x, bc[i].y, bc[idr].x, bc[idr].y);
      }
      staze[mojid].v.pb(i);

      r[mojid].x=bc[i].x;
      r[mojid].y=bc[i].y;
   }
//   int smica=0;
//   for(int i=1; i<=k; i++){
//      cout<<"staza: "<<i<<" ";
//      cout<<staze[i].v.size()<<" "<<staze[i].duzina<<endl;
//      smica+=staze[i].v.size();
//   }
//   deb(smica);
//   cout<<endl;
}
void podela_na_max_dub(){ //1 za speed, 0 za staze
   kolko=k/(1<<(max_dub-1));
   ostatak=k%(1<<(max_dub-1));
   rekurzivno(1, n, 1, 0); //sredjena postavka
   sort(bc+1, bc+1+n, cmp_bc_id);
   izracunaj_cnt_grupice();
//   sortiraj_r();
   namesti_pocetne_koordinate();
   trazenje_najbrzeg_runera();
   konacna_raspodela();
}
int suprotran(int x){
   if(x==0) return 2;
   else return 1;
}
void prekalkulisi(int okle){
   int kraj=min(okle-2, granica_dp-1);
   float swapalica, pret=0, sled;
   swapalica=dist(bc[okle-1].x, bc[okle-1].y, bc[okle-2].x, bc[okle-2].y);
   for(int i=1; i<=kraj; i++){
      sled=pd[i];
      pd[i]=pret+swapalica;
      pret=sled;
   }
}
void nadji_res_xy(){
   res[1].x=res[2].x=-1;
   for(int i=1; i<=n; i++){
      if(bc[i].idrunera==1 && res[1].x==-1){
         res[1].x=bc[i].x;
         res[1].y=bc[i].y;
      }
      if(bc[i].idrunera==2 && res[2].x==-1){
         res[2].x=bc[i].x;
         res[2].y=bc[i].y;
      }
      if(res[1].x!=-1 && res[2].x!=-1) return;
   }
}
void odredi_ko_kome(){
   int tren=1, pos=n, sled, zapostaviti, sledtren;
   if(dp[0][n].score<dp[1][n].score) tren=0;
   //ako je t jednak sa dp[pos].t onda ide suprotran na interval, else ide isti
   while(pos>1){
      sled=dp[tren][pos].iksd;
      sledtren=dp[tren][pos].t;
      zapostaviti=dp[tren][pos].sta_je_izmedju;
      if(tren!=sledtren){
         bc[pos].idrunera=zapostaviti;
         if(zapostaviti==1) bc[sled].idrunera=2;
         else bc[sled].idrunera=1;
      }
      else{
         if(zapostaviti==2) bc[sled].idrunera=bc[pos].idrunera=1;
         else bc[sled].idrunera=bc[pos].idrunera=2;
      }
      for(int j=sled+1; j<=pos-1; j++) bc[j].idrunera=zapostaviti;
//      bc[sled].idrunera=bc[pos].idrunera=tren;
      pos=sled;
      tren=sledtren;
   }
}
void postavi(bool t, int a, int b){  //a->b   a>=b
   float d_ij_i=dist(bc[a].x, bc[a].y, bc[b].x, bc[b].y);
   if(a==b) d_ij_i=0;
   trenic.iksd=b;

   trenic.sta_je_izmedju=suprotran(t);
   trenic.t=t;

   trenic.score=dp[t][b].score+d_ij_i*s[t];
   if(b+1==a) trenic.prev=dp[t][b].prev;
   else{
      trenic.prev=a-1;
      if(dp[t][b].prev!=0)
         trenic.score+=dist(bc[dp[t][b].prev].x, bc[dp[t][b].prev].y, bc[b+1].x, bc[b+1].y)*s[(!t)];
      trenic.score+=pd[max(a-b-2, 1)]*s[(!t)];
   }
   if(trenic.score<dp[t][a].score) dp[t][a]=trenic;

//   ___________________________________
   trenic.score=dp[!t][b].score;
   trenic.prev=b;
   trenic.t=!t;
   trenic.sta_je_izmedju=t+1;
   if(dp[!t][b].prev!=0) trenic.score+=dist(bc[dp[!t][b].prev].x, bc[dp[!t][b].prev].y, bc[b+1].x, bc[b+1].y)*s[t];

   if(b+1 < a){
      trenic.score+=pd[max(a-b-2, 1)]*s[t];
      trenic.score+=dist(bc[a].x, bc[a].y, bc[a-1].x, bc[a-1].y)*s[t];
   }

   if(trenic.score<dp[t][a].score) dp[t][a]=trenic;
//   ___________________________________
//   trenic.score=dp[!t][b].score;
//   trenic.prev=a-1;
//   trenic.sta_je_izmedju=suprotran(t);
//   trenic.t=!t;
//   if(dp[!t][b].prev!=0) trenic.score+=dist(bc[dp[!t][b].prev].x, bc[dp[!t][b].prev].y, bc[a].x, bc[a].y)*s[t];
//
//   if(b+1 < a){
//      trenic.score+=pd[max(a-b-2, 1)]*s[!t];
//      trenic.score+=dist(bc[b].x, bc[b].y, bc[b+1].x, bc[b+1].y)*s[!t];
//   }
//
//   if(trenic.score<dp[t][a].score) dp[t][a]=trenic;
}
void kje2(){   //dinamika hehehe
   dp[0][1].score=dp[1][1].score=0;
   for(int i=2; i<=n; i++) dp[0][i].score=dp[1][i].score=1e15;
   int kraj;
   s[0]=r[1].s; s[1]=r[2].s;

   for(int i=2; i<=n; i++){
      kraj=min(granica_dp, i);
      prekalkulisi(i);
      for(int j=1; j<=kraj; j++){   //prvo 1
         postavi(0, i, i-j);
         postavi(1, i, i-j);
      }
   }

   odredi_ko_kome();
   nadji_res_xy();

   staze[1].v.clear();
   staze[2].v.clear();
   staze[1].duzina=staze[2].duzina=0;
   for(int i=1; i<=n; i++){
      if(staze[bc[i].idrunera].v.size()!=0){
         kraj=staze[bc[i].idrunera].v[staze[bc[i].idrunera].v.size()-1];
         staze[bc[i].idrunera].duzina+=dist(bc[kraj].x, bc[kraj].y, bc[i].x, bc[i].y);
      }
      staze[bc[i].idrunera].v.pb(i);
   }

   sort(staze+1, staze+1+k, cmp_staze_rastuce);   //moze ovo ne treba ovde, mislim sigurno ne treba
   sort(r+1, r+1+k, cmp_r_opadajuce);   //moze ovo ne treba ovde, mislim sigurno ne treba

   for(int i=1; i<75; i++) optimizacija(1, 2);
   konacna_raspodela();
}
int main(){
   cout<<setprecision(1)<<fixed;
//   tin=1;
   vreme0=clock();
   unos();

   if(k==2) kje2();
   else if(test<=3){
//      return 23;
      algoritam_najblizi_put_bez_staza_samo_najblizi();
   }
   else{
      if(test==4) max_dub=4;
//      deb(max_dub);
//      if(k<=60000){
//         podela_na_max_dub();   //slicno je kao delovi kod sis al je bolje (nadam se)
//      }
//      else return 45;
      if(k>60000) delovi_koordinatnog_sistema();
      else{
         podela_na_max_dub();   //slicno je kao delovi kod sis al je bolje (nadam se)
      }
   }
   ispis();
   return 0;
}