#include<cstdio>
#include<functional>
#include<utility>
#include<algorithm>
#include<set>
using namespace std;
using ll = long long;
using ull = unsigned long long;

int main(){
    int N, M;
    scanf("%d %d", &N, &M);
    pair<int, int> pawn[M];
    for (unsigned i = 0; i < M; i++) scanf("%d %d", &pawn[i].first, &pawn[i].second);
    set<int> valid_y;
    valid_y.insert(N);
    sort(pawn, pawn + M);
    bool pawn_exists_in_front = false, pawn_exists_in_left;
    for(unsigned i = 0;i < M;i++){
        pawn_exists_in_left = pawn_exists_in_front;
        pawn_exists_in_front = (valid_y.find(pawn[i].second) != valid_y.end()) && i < M-1 && pawn[i+1] == make_pair(pawn[i].first, pawn[i].second + 1);
        if(((i && pawn[i-1] == make_pair(pawn[i].first, pawn[i].second - 1)) ? pawn_exists_in_left : (valid_y.find(pawn[i].second - 1) != valid_y.end())) || (valid_y.find(pawn[i].second + 1) != valid_y.end())) valid_y.insert(pawn[i].second);
        else valid_y.erase(pawn[i].second);
    }
    printf("%u\n", valid_y.size());
	return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
long long n, k;
int arr[9][9] = {0,};
int visited[9]={0,};
int answer=0;
void dfs(int node, long long times){
  if(node<0 || node>=n || times>k){return;}
  if(visited[node]==1) return ;
  for(int i=0; i<n; i++){
    if(i == node){continue;}
    if(i==0 && visited[i]==1 && times+arr[node][i] == k){
      answer++;
      continue;
    }
    if(visited[i]==0){
        visited[node] =1;
        dfs(i, times+arr[node][i]);
        visited[node] = 0;

    }
  }
  return;
}
int main(){
  
  cin>>n>>k;
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      cin>> arr[i][j];
    }
  }
  dfs(0,0);
  cout <<answer<<endl;
}