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

int verifica_solucao(float * tam_tarefa, int num_tarefas, float capacidade_maquina, int * maquina_por_tarefa){
  float * carga_por_maquina = (float*) calloc(num_tarefas, sizeof(float));
  for(int i = 0; i < num_tarefas; i++){
    if(maquina_por_tarefa[i] != -1) carga_por_maquina[maquina_por_tarefa[i]] += tam_tarefa[i];
  }
  int maior_maquina = 0;
  for(int m = 0; m < num_tarefas; m++){
    if(carga_por_maquina[m] > 0) maior_maquina = m;
  }
  free(carga_por_maquina);
  return maior_maquina+1;
}

float carga_maquina(float * tam_tarefa, int num_tarefas, int id_maquina, int * maquina_por_tarefa){
  float carga = 0;
  for(int i = 0; i < num_tarefas; i++){
    if(maquina_por_tarefa[i] == id_maquina)
    carga += tam_tarefa[i];
  }
  return carga;
}
  
  
int limitante_inferior(float * tam_tarefa, int num_tarefas, float capacidade_maquina){
  float soma = 0;
  for(int i = 0; i < num_tarefas; i++){
    soma += tam_tarefa[i];
  }
  return (int) ceil(soma/capacidade_maquina);
}

int limitante_superior1(float * tam_tarefa, int num_tarefas, float capacidade_maquina, int * maquina_por_tarefa){
  for(int i = 0; i < num_tarefas; i++){
    maquina_por_tarefa[i] = i;
  }
  return verifica_solucao(tam_tarefa, num_tarefas, capacidade_maquina, maquina_por_tarefa);
}


int limitante_superior2(float * tam_tarefa, int num_tarefas, float capacidade_maquina, int * maquina_por_tarefa){
  int ultima_maquina_utilizada = 0;
  for(int i = 0; i < num_tarefas; i++){
    if(carga_maquina(tam_tarefa, num_tarefas, ultima_maquina_utilizada, maquina_por_tarefa) + tam_tarefa[i] <= capacidade_maquina){
      //cabe na mesma maquia
      maquina_por_tarefa[i] = ultima_maquina_utilizada;
    }else{
      //nao cabe, inaugura uma nova
      ultima_maquina_utilizada++;
      maquina_por_tarefa[i] = ultima_maquina_utilizada;
    }
  }
  return verifica_solucao(tam_tarefa, num_tarefas, capacidade_maquina, maquina_por_tarefa);
}

int limitante_superior3(float * tam_tarefa, int num_tarefas, float capacidade_maquina, int * maquina_por_tarefa){
  for(int i = 0; i < num_tarefas; i++){
    int maquina = 0;
    while(carga_maquina(tam_tarefa, num_tarefas, maquina, maquina_por_tarefa) + tam_tarefa[i] > capacidade_maquina){
      maquina++;
    }
    maquina_por_tarefa[i] = maquina;
  }
  return verifica_solucao(tam_tarefa, num_tarefas, capacidade_maquina, maquina_por_tarefa);
}


int melhor;

int backtracking(float * tam_tarefa, int num_tarefas, float capacidade_maquina, int * maquina_por_tarefa, int tarefa_atual, int num_maquinas){
  if(tarefa_atual == num_tarefas + 1){
    //solucao completa
    int resultado = verifica_solucao(tam_tarefa, num_tarefas, capacidade_maquina, maquina_por_tarefa);
    if(resultado < melhor) melhor = resultado;
    return resultado;
  }
  
  for(int m = 0; m < num_maquinas; m++){
    //tentar empacotar a tarefa i na maquina m
    if(carga_maquina(tam_tarefa, num_tarefas, m, maquina_por_tarefa) + tam_tarefa[tarefa_atual] > capacidade_maquina){
      //se não cabe, poda por inviabilidade
      continue;
    }
    maquina_por_tarefa[tarefa_atual] = m;
    //se coube tenta empacotar a proxima tarefa
    int solucao = backtracking(tam_tarefa, num_tarefas, capacidade_maquina, maquina_por_tarefa, tarefa_atual+1, num_maquinas);
    if(solucao < melhor) melhor = solucao;
    //remove a tarefa para tentar na proxima
    maquina_por_tarefa[tarefa_atual] = -1;
  }
  return melhor;
}

int bnb(float * tam_tarefa, int num_tarefas, float capacidade_maquina, int * maquina_por_tarefa, int tarefa_atual, int num_maquinas){
  if(tarefa_atual == num_tarefas){
    //solucao completa
    int resultado = verifica_solucao(tam_tarefa, num_tarefas, capacidade_maquina, maquina_por_tarefa);
    if(resultado < melhor) melhor = resultado;
    return resultado;
  }
  
  for(int m = 0; m < num_maquinas; m++){
    if(m > tarefa_atual){
      //quebra de simetria
      continue;
    }
    if(m+1 >= melhor){
      //poda por limitante
      continue;
    }
    //tentar empacotar a tarefa i na maquina m
    if(carga_maquina(tam_tarefa, num_tarefas, m, maquina_por_tarefa) + tam_tarefa[tarefa_atual] > capacidade_maquina){
      //se não cabe, poda por inviabilidade
      continue;
    }
    maquina_por_tarefa[tarefa_atual] = m;
    //se coube tenta empacotar a proxima tarefa
    int solucao = bnb(tam_tarefa, num_tarefas, capacidade_maquina, maquina_por_tarefa, tarefa_atual+1, num_maquinas);
    if(solucao < melhor) melhor = solucao;
    //remove a tarefa para tentar na proxima
    maquina_por_tarefa[tarefa_atual] = -1;
  }
  return melhor;
}

int exato(float * tam_tarefa, int num_tarefas, float capacidade_maquina, int * maquina_por_tarefa){
  int limitante_superior = limitante_superior3(tam_tarefa, num_tarefas, capacidade_maquina, maquina_por_tarefa);
  melhor = limitante_superior;
  
  for(int i = 0; i < num_tarefas; i++) maquina_por_tarefa[i] = -1;  
  maquina_por_tarefa[0] = 0;
  int resultado = bnb(tam_tarefa, num_tarefas, capacidade_maquina, maquina_por_tarefa, 1, limitante_superior);
  return melhor;
}


int main(int * argc, char * argv[]){
  float capacidade_maquina;
  int num_tarefas;
  float * tam_tarefa;

  scanf("%f %d", &capacidade_maquina, &num_tarefas);
  tam_tarefa = (float*) malloc(sizeof(float) * num_tarefas);  
  
  for(int i = 0; i < num_tarefas; i++){
    scanf("%f", &(tam_tarefa[i]));
  }
    
  
  
  printf("limitante inferior %d\n", limitante_inferior(tam_tarefa, num_tarefas, capacidade_maquina));
  
  int * maquina_por_tarefa = (int*) malloc(sizeof(int)*num_tarefas);
  for(int i = 0; i < num_tarefas; i++) maquina_por_tarefa[i] = -1;
  
  printf("limitante superior 01 = %d\n", limitante_superior1(tam_tarefa, num_tarefas, capacidade_maquina, maquina_por_tarefa));
  
  for(int i = 0; i < num_tarefas; i++) maquina_por_tarefa[i] = -1;
  printf("limitante superior 02 = %d\n", limitante_superior2(tam_tarefa, num_tarefas, capacidade_maquina, maquina_por_tarefa));

  for(int i = 0; i < num_tarefas; i++) maquina_por_tarefa[i] = -1;  
  printf("limitante superior 03 = %d\n", limitante_superior3(tam_tarefa, num_tarefas, capacidade_maquina, maquina_por_tarefa));
  
  for(int i = 0; i < num_tarefas; i++) maquina_por_tarefa[i] = -1;    
  printf("exato = %d\n", exato(tam_tarefa, num_tarefas, capacidade_maquina, maquina_por_tarefa));
  
  free(maquina_por_tarefa);
  free(tam_tarefa);
  return 0;
}