Dragančetu je dosadilo da živi u gradu pa je rešio da sagradi sebi vikendicu, u kojoj će u miru i tišini moći da sprovodi svoje programerske ideje. Kako je Draganče veoma vredan, rešio je da sam napravi nacrte njegove kuće iz snova. No, na početku je trebalo da odredi mesto na kome će se graditi. Kako Draganče nije baš bogat (matematika i programiranje nije bilo isplativo kako je on mislio), odredio je maksimalni budžet koji može da potroši za kupovinu placeva. Naravno, želi da vikendica bude što lepša, pa je odredio i donju granicu budžeta. Sad je u nedoumici gde da je sagradi. Pomozite Dragančetu da odredi broj mogućih mesta za gradnju vikendice.

Mesta na kojima Draganče može da gradi vikendicu data su u obliku pravougane matrice, gde polja predstavljaju placeve. Za svaki plac je data njegova cena. Vikendica je u obliku pravougaonika. Na pravougaoniku se može sagraditi vikendica ukoliko suma njenih parcela upada u granice budžeta.

Ulaz:

(Ulazni podaci se nalaze u datoteci vikendica.in) U prvom redu se nalaze četiri broja: n, m, A i B, koji predstavljaju broj vrsta i kolona matrice, donju granicu i gornju granicu budžeta. U narednih n redova nalazi se po m nenegativnih celih brojeva koji predstavljaju cene placeva.

Izlaz:

(Izlazne podatke upisati u datoteku vikendica.out) U prvom i jedinom redu štampati broj mogućih pozicija vikendice.

Ograničenja:

• 1 ≤ n, m ≤ 150
• 0 ≤ A ≤ B ≤ 10⁹
• cene placeva su u opsegu [0, 10⁴]
• broj rešenja ne prelazi 2³⁰
• ukupna suma cena svih placeva je manja od 2³⁰
• vremensko ograničenje za izvršavanje programa je 1 s.

Primer 1:

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

7

Objašnjenje:

Moguće pozicije za vikendicu (predstavljene sa 'o') su sledeće:

oox ooo oox xxx xoo xxx ooo
oox ooo oox xoo xoo ooo ooo
xxx xxx oox xoo xoo ooo ooo

Suma elemenata u označenim pravougaonicima je u opsegu [2,3].

Primer 2:

3 4 7 10
1 3 4 2
3 4 5 2
1 3 4 1

16

/*
  DRZAVNO TAKMICENJE 2007
  ZADATAK: vikendica
  AUTOR: Andreja Ilic, Nis

    Svaki pristup zadatku vodi do problema kako da se izracuna zbir cena u 
  odredjenom pravougaoniku. Zato cemo umesto samih cena placeva u matrici d pamtiti 
  sume odredjenih pravougaonika, tacnije element d [i][j] ce nam predstavljati 
  sumu cena u pravougaoniku sa temenima: (1,1), (i,1), (j,1), (i,j). Ovu sumu
  mozemo racunati preko formule
  
         d [i][j] = d [i - 1][j] + d [i][j - 1] - d [i - 1][j - 1] + cena [i][j];
         
    Sada mozemo linearno racunati cenu bilo kog pravougaonika. U kodu, funkcija 
  Sum (x1, y1, x2, y2) nam vraca zbir cune u pravougaoniku cije je gornje levo polje 
  (x1, y1) a donje desno (x2, y2).
       
      Vratimo se glavnom problemu. Njemu pristupamo na sledeci nacin: za svako polje
  (i, j) racunamo koliko pravougaonika postoje koji zadovoljavaju trazeni uslov,
  tako da je polje (i, j) bas donje desno polje. Naravno isporbacemo sve moguce sirine 
  pravougaonika ali za njenu duzinu necemo isporabavati sve mogucnosti. Naime, kada trazimo
  broj resenja sa sirinu k mi znamo da je njena duzina sigurno manja od duzine za
  sirinu k - 1 (jer su cene nenegativne, pa je samim tim i suma rastuca) tako da cemo 
  samo te mogucnosti isprobavati.
  
    Dakle, napravimo funkciju koja ce nam vracati broj prvougaonika koji imaju cenu
  manju ili jednaku od date vrednosti. Kao rezultat vratimo razliku tih funkvija za
  vrednosti B i A - 1.
  
      Vremenska slozenost algoritma je O (n^2 +  n^3), dok je memorijska slozenost O (n^2).
*/

#include <stdio.h>
#define MaxN 205

int n, m, A, B, d [MaxN][MaxN];
FILE *in, *out;

  int Sum (int x1, int y1, int x2, int y2)
  {
    return (d [x2][y2] - d [x1 - 1][y2] - d [x2][y1 - 1] + d [x1 - 1][y1 - 1]);
  }

  int Count (int Max)
  {
    int sol = 0, i, j, k, l;

    for (i = 1; i <= n; i++)
      for (j = 1; j <= m; j++)
      {
        k = 1;
        for (l = i; l >= 1; l--)
        {
          while ((k <= j) && (Sum (l, k, i, j) > Max))
            k++;
          if (k > j) break;
          sol = sol + (j - k + 1);
        }
      }
    return sol;
  }

  int main ()
  {
    int x, i, j;
    
    in = fopen ("vikendica.in", "r");
    out = fopen ("vikendica.out", "w");
    fscanf (in, "%d %d %d %d", &n, &m, &A, &B);
    
    for (i = 1; i <= n; i++)
      for (j = 1; j <= m; j++)
      {
        fscanf (in, "%d", &x);
        d [i][j] = d [i - 1][j] + d [i][j - 1] - d [i - 1][j - 1] + x;
      }
    fprintf (out, "%d\n", Count (B) - Count (A - 1));
    
    return 0;
  }