for(int i=1;i<=n;i++)

{

int ny=0,nx=i;

while(ny!=(h+1))

{

if(arr[1][ny][nx-1]&&arr[0][ny][nx])

nx-=1;

else if(arr[1][ny][nx]&&arr[0][ny][nx+1])

nx+=1;

ny+=1;

}

if(nx!=i)

return false;

}

return true;

if (fun())

ans = min(cnt, ans);

if (cnt >= 3)

return;

// 가지치기 1 ( cnt가 4인 노드를 만들지 않는다.)

int tmp=cur;

while(tmp<n*h-h)

// 가지치기 2 ( 순열이 아닌 조합으로 조작해야한다.)

{

int i=tmp/h+1,j=tmp%h+1;

// 높이가 h로 나눈 몫을 세로 선, 나머지를 가로 선으로 한다.

if (!(arr[1][j][i] * arr[0][j][i + 1]) && !(arr[1][j][i - 1] * arr[0][j][i]) &&!(arr[1][j][i + 1] * arr[0][j][i + 2])) {

arr[1][j][i] = arr[0][j][i + 1] = 1;

dfs(cnt + 1, tmp+1);

arr[1][j][i] = arr[0][j][i + 1] = 0;

}

tmp++;

}

// 입력을 받아온다.

scanf("%d%d%d",&n,&m,&h);

for(int i=0;i<m;i++){

scanf("%d%d",&a,&b);

arr[1][a][b]=arr[0][a][b+1]=1;

}

// dfs를 시작한다.

dfs(0,0);

if(ans>3)

printf("-1");

else

printf("%d",ans);

return 0;

}