Vikendica
vreme | memorija | ulaz | izlaz |
---|---|---|---|
0,5 s | 256 Mb | standardni izlaz | standardni ulaz |
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.
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.
U prvom i jedinom redu štampati broj mogućih pozicija vikendice.
- 1 ≤ n, m ≤ 150
- 0 ≤ A ≤ B ≤ 10^9
- cene placeva su u opsegu [0, 10^4]
- broj rešenja ne prelazi 2^30
- ukupna suma cena svih placeva je manja od 2^30
3 3 2 3
1 0 0
0 1 0
0 0 1
7
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].
Morate biti ulogovani kako biste poslali zadatak na evaluaciju.