#include <stdio.h>
#include <string.h>

const unsigned int dva_na[16] = { 1,2,4,8,16,32,64,128,256,512,1024,2048,
                                  4096,8192,16384,32768u };

char niz[16];
int n,duljina_niza;
int rjesenje;

void ucitaj_podatke(void)
{
  FILE *fp;

  fp = fopen("SVOP.IN","rt");

  fscanf(fp,"%s%u",niz,&n);

  fclose(fp);
}

void promjena_stanja(int staro_stanje,int *novo_stanje,int indeks)
{
  int i;

  *novo_stanje = 0;

  for (i = 0;i < indeks;++i)
    if (staro_stanje & dva_na[i])
      *novo_stanje |= dva_na[i];

  for (i = 0;i < n;++i)
    if (staro_stanje & dva_na[indeks + i])
      *novo_stanje |= dva_na[indeks + n - i - 1];

  for (i = indeks + n;i < duljina_niza;++i)
    if (staro_stanje & dva_na[i])
      *novo_stanje |= dva_na[i];
}

void rijesi(void)
{
  int i;
  unsigned int broj_stanja;
  char tablica[32767];
  int stanje,trazeno_stanje,novo_stanje;
  int potez;
  int ima_jos;

  duljina_niza = strlen(niz);
  broj_stanja = dva_na[duljina_niza];

  for (i = 0;i < broj_stanja;++i)
    tablica[i] = -1;

  stanje = 0;
  for (i = 0;i < duljina_niza;++i)
    stanje = 2 * stanje + (niz[i] - '0');

  trazeno_stanje = 0;
  for (i = 0;i < duljina_niza;++i)
    if (niz[i] - '0')
      trazeno_stanje = 2 * trazeno_stanje + 1;

  for (i = 0;i < duljina_niza;++i)
    if (!(niz[i] - '0'))
      trazeno_stanje = 2 * trazeno_stanje;

  rjesenje = -1;

  if (stanje == trazeno_stanje)
  {
    rjesenje = 0;

    return;
  }

  tablica[stanje] = 0;
  potez = 0;

  do
  {
    ima_jos = 0;

    for (stanje = 0;stanje < broj_stanja;++stanje)
      if (tablica[stanje] == potez)
      {
        for (i = 0;i < duljina_niza - n + 1;++i)
        {
          promjena_stanja(stanje,&novo_stanje,i);

          if (tablica[novo_stanje] == -1)
          {
            if (novo_stanje == trazeno_stanje)
            {
              rjesenje = potez + 1;

              return;
            }

            ima_jos = 1;

            tablica[novo_stanje] = potez + 1;
          }
        }
      }

    ++potez;

  } while (ima_jos);

}

void zapisi_rjesenje(void)
{
  FILE *fp;

  fp = fopen("SVOP.OUT","wt");

  fprintf(fp,"%d\n",rjesenje);

  fclose(fp);
}

int main(void)
{
  ucitaj_podatke();
  rijesi();
  zapisi_rjesenje();

  return 0;
}