N×M rūtiņas liela tabula aizpildīta ar veseliem nenegatīviem skaitļiem. Nepieciešams noteikt, cik veidos šajā tabulā iespējams atrast taisnstūrveida rūtiņu apgabalu, kura rūtiņās ierakstīto skaitļu summa būtu vismaz A, bet nepārsniegtu B (A un B - veseli nenegatīvi skaitļi, A≤B). Taisnstūrveida apgabals var būt arī viena atsevišķa rūtiņa vai visa tabula.

Uzrakstiet programmu, kas atrod aprakstīto taisnstūru skaitu!

Pirmajā rindā dotas veselu nenegatīvu skaitļu N (tabulas rindu skaits, 1≤N≤300), M (tabulas kolonnu skaits, 1≤M≤300), A (mazākā pieļaujamā summas vērtība) un B (lielākā pieļaujamā summas vērtība, A≤B≤2×10⁹ ). Katri divi blakus skaitļi ir atdalīti ar tukšumzīmi. Nākamajās N rindās dots tabulas rūtiņās ierakstīto skaitļu apraksts. Katrā no šīm rindām doti M veseli nenegatīvi skaitļi, kur katri divi blakus skaitļi atdalīti ar tukšumzīmi. Katram n(1≤n≤N) un m(1≤m≤M) skaitlis ievaddatu n+1-ās rindas m-tais skaitlis pēc kārtas ir ierakstīts tabulas n-tās rindas m-tās kolonnas rūtiņā. Zināms, ka tabulā ierakstīto skaitļu kopsumma nepārsniedz 2×10⁹ .

Vienīgajā rindā jāizvada vesels nenegatīvs skaitlis - derīgo taisnstūrveida apgabalu skaits

Uzdevums no: LATVIJAS 31.INFORMĀTIKAS NOVADA OLIMPIĀDES VECĀKĀS (11.-12. KLAŠU) GRUPAS