#include <stdio.h>
#include <stdlib.h>

int a,b,c,k,n,tot,min,bra,sum,oen,t[101],m[20],p[20];

int main(){
  printf("Antal partier ? ");
  scanf("%d",&n);
  tot=0;
  for(a=0;a<n;a++) {
    printf("Parti %d, mandat ? ", a+1);
    scanf("%d",&m[a]);
    tot+=m[a];
    printf("Parti %d, position ? ", a+1);
    scanf("%d",&p[a]);
  }
  min=100*n;
  for(b=0;b<(1<<n);b++){  //Loopa over alla 2^n regeringar
    sum=0;
    for(c=0;c<=100;c++) t[c]=0;
    k=0;
    for(a=0;a<n;a++) if((b & (1<<a)) >0){  //Om parti a ingar
      sum+=m[a];  // sum samlar ihop hur manga mandat regeringen har
      k++;        // k samlar ihop hur manga partier som ingar
      t[p[a]]++;  // t samlar ihop hur manga ingaende partier som 
                  // ligger pa varje position
    }
    if(sum*2>=tot){ //Har regeringen majoritet?
      a=0;
      for(c=0;c<=100;c++) { //Loopa over alla positioner c
	a+=t[c];   //Samla ihop hur manga partier som ligger <=c
	if(a>k/2) break;  //Ligger mer an halften <=c, da ar c medianen
      }
      oen=0;
      for(a=0;a<n;a++) if((b & (1<<a)) >0) 
	oen+=abs(p[a]-c); //Summera upp oenigheten
      if(oen<min) {  //Ar det den lagsta oenigheten hittills?
	min=oen;
	bra=b;
      }
    }
  }
  printf("Basta regeringen: ");
  for(a=0;a<n;a++) if((bra & (1<<a)) >0) printf("%d ",a+1);
  printf("\n");
  return 0;
}