Robotić WALL-E se nalazi na deponiji smeća koja je prikazana u obliku matrice dimenzije n x m. Kako je jedna od karakteristika deponija neurednost, neka polja su nepodesna za kretanje, tako da WALL-E ne može prelaziti preko njih. WALL-E-u je dosadno pa je rešio da se malo poigra. Naime, zadaje sebi niz d prirodnih brojeva dužine k koji označavaju broj koraka. Robotić može sa polja u matrici da se kreće u četiri pravca: gore, dole, levo i desno. U i-tom trenutku WALL-E mora da napravi d[i] koraka u jednom od četiri pravaca. Naravno, u toku tih d[i] koraka WALL-E ne sme preći preko polja na kojima je zabranjeno kretanje. WALL-E-ja zanima na koliko različitih polja može biti u k-tom trenutku ukoliko kretanje započinje sa startnog polja (startX, startY).

Ulaz:

(Ulazni podaci se učitavaju iz datoteke robotic.in.) U prvom redu nalaze se četiri prirodna broja n, m, startX i startY (1 ≤ n,m ≤ 200, 1 ≤ startX ≤ n, 1 ≤ startY ≤ m) koji predstavljaju dimenzije matrice i koordinate startnog polja. Narednih n redova sadrže po m brojeva 1 ili 0, koji opisuju polja matrice: 0 označava da se preko polja može preći, a 1 označava polje na kome je zabranjeno kretanje. U (n + 2)-om redu se nalazi prirodni broj k (1 ≤ k ≤ 200) koji označava dužinu niza d. Naredni red sadrži k prirodnih brojeva odvojenih po jednim znakom razmaka koji označavaju elemente niza d.

Izlaz:

(Izlazni podaci se ispisuju u datoteku robotic.out.) U prvom i jedinom redu ispisati jedan prirodan broj koji predstavlja broj različitih polja na kojima WALL-E može da bude u k-tom trenutku.

Primer:

3 3 1 1
0 1 0
0 0 0
0 0 0
3
1 2 1

3

Objašnjenje.

WALL-E može završiti na poljima sa koordinatama (1, 3), (2, 2) i (3, 3). Navedene krajnje pozicije kao i putanje kojima dolazi do njih su prikazani na slici.

/*
  Author: Andreja Ilic, PMF Nis
  e-mail: ilic_andrejko@yahoo.com

  Algorithm: 
  Zadatak resavamo BFS pretragom. Za svaki trenutak pamtimo listu 
  moguci pozicija, na osnovu kojih racunamo pozicije za naredni 
  trenutak. Ispitivanje moguceg poteza sa polja (x, y) na polje 
  (x1, y1) svodimo na ispitivanje da li je suma elemenata u toj 
  podmatrici 0 ili ne. Ovo mozemo  odraditi pomocu predprocesiranja 
  u O(1) (pamcenjem prefiksnih suma sa redove i kolone). 

  Complexity: O(n^2 * k)
*/


#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;

#define MAX_N 205

struct cell
{
  int x, y;
} Cell;

int n, m, startX, startY, sol = 0, k;
int board [MAX_N][MAX_N], d [MAX_N], prefixRow [MAX_N][MAX_N], prefixColumn [MAX_N][MAX_N];
int dx [] = {0, 1, 0, -1};
int dy [] = {1, 0, -1, 0};

  // Unos podataka
  void input()
  {
    FILE *in = fopen ("robotic.in", "r");
    fscanf (in, "%d %d %d %d", &n, &m, &startX, &startY);
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= m; j++)
        fscanf(in, "%d", &board[i][j]);
    fscanf(in, "%d", &k);
    for (int i = 0; i < k; i++)
      fscanf (in, "%d", &d [i]);
    fclose(in);
  }

  // Ispis resenja
  void output()
  {
    FILE *out = fopen("robotic.sol", "w");
    fprintf (out, "%d\n", sol);
    fclose(out);
  }

  // Inicijalizacija prefiksnih suma za redove i kolone
  void intializationOfPrefixSums()
  {
    for (int i = 1; i <= n; i++)
    {
      prefixRow [i][0] = 0;
      for (int j = 1; j <= m; j++)
        prefixRow [i][j] = prefixRow [i][j - 1] + board [i][j];
    }
    for (int j = 1; j <= m; j++)
    {
      prefixColumn [j][0] = 0;
      for (int i = 1; i <= n; i++)
        prefixColumn [j][i] = prefixColumn [j][i - 1] + board [i][j];
    }
  }

  // Funkcija minimuma
  int min(int a, int b)
  {
    if (a < b)
      return a;
    return b;
  }

  // Funkcija maxkimuma
  int max(int a, int b)
  {
    if (a > b)
      return a;
    return b;
  }

  // Suma elemenata u matrici od polja (a,b) do (c,d)
  int sum (int a, int b, int c, int d)
  {
    if (a == c)
      return prefixRow [a][max(b, d)] - prefixRow [a][min(b, d) - 1];
    return prefixColumn [b][max(a, c)] - prefixColumn[b][min(a, c) - 1];
  }

  // Glavna metoda
  void solve()
  {
    intializationOfPrefixSums();
    cell q [2][MAX_N * MAX_N];
    int num [2];

    q [0][0].x = startX; q [0][0].y = startY;
    num [0] = 1;

    bool mark [MAX_N][MAX_N];
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= m; j++)
        mark [i][j] = false;

    for (int index = 0; index < k; index++)
    {
      int  nextIndex = (index + 1) % 2;
      for (int i = 0; i < num[index % 2]; i++)
        mark [q [(index % 2)][i].x][q [(index % 2)][i].y] = false;

      int t = 0;
      num [nextIndex] = 0;
      while (t < num [index % 2])
      {
        cell currentCell = q [index % 2][t];
        int x = currentCell.x, y = currentCell.y;

        for (int i = 0; i < 4; i++)
        {
          int x1 = x + dx [i] * d [index];
          int y1 = y + dy [i] * d [index];
          if ((1 <= x1) && (x1 <= n) && (1 <= y1) && (y1 <= m))
            if ((! mark [x1][y1]) && (sum (x, y, x1, y1) == 0))
            {
              q [nextIndex][num [nextIndex]].x = x1;
              q [nextIndex][num [nextIndex]].y = y1;
              num[nextIndex]++;
              mark [x1][y1] = true;
            }
        }
        t++;
      }
    }

    sol = num [k % 2];
  }

int main()
{
  input();
  solve();
  output();

  return 0;
}