Подморница
Ана и Миа ја играат играта Подморница. Миа има поставено една подморница со големина LxK во матрица со NxM полиња. Подморницата може да биде поставена вертикално или хоризонтално.
Задачата на Ана е да најде каде е поставена подморницата. Ана до овој момент направила P обиди да погоди некое поле од подморницата. Во i-тиот обид, Ана го кажува редот X[i] и колоната Y[i] . Секој следен обид на Ана е за позиција различна од претходните. После секој обид Миа кажува дали со обидот Ана погодила поле од подморницата или не. Познато е дека сите P обиди на Ана биле промашување.
Земајќи ги предвид сите полиња - промашувања, на кои не може да се најде дел од подморницата, пресметајте колку различни места во матрицата, на кои може да биде поставена подморницата, постојат моментално?
Забелешка за квадратна подморница: Квадратно место на кое квадратна подморница може да се постави во хоризонтала или во вертикала се брои точно еднаш.
Влез
Во првиот ред е дадена големината на матрицата на играта Подморница: броевите N и M, одделени со едно празно место (1 <= N,M <= 10 000)
Во вториот ред е дадена големината на подморницата: броевите L и K, одделени со едно празно место (1 <= L<=N,1<= K <= M)
Во третиот ред е даден бројот на обиди P (1 <= P <= 100 000) кои што ги направила Ана.
Во секој од следните P редови дадени се по два броја X[i] и Y[i], одделени со по едно празно место, 1 <= i <= P.
Забелешка:
Во 40% од случаите, 1 <= N,M <= 50
Во 30% од случаите, L=1 или K = 1, 50 <= N,M <= 10000
Во 30% од случаите, L > 1, K > 1 , 50 <= N,M <= 10000
Излез
Во првиот и единствен ред се печати бројот на места на кои може да биде поставена подморницата моментално.
Ограничувања
Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes
Примери
влез 4 4 2 2 4 1 1 2 4 3 1 4 3 | излез 2 |
влез 3 3 2 1 3 1 1 2 3 3 1 | излез 5 |
Објаснување на првиот тест пример: Играта подморница се игра во матрица со димензии 4x4. Ана имала 4 обиди каде подморницата не била погодена. Овие обиди се дадени со x на сликата. Има две можности каде може да се наоѓа подморницата со димензии 2x2 (обоени на сликата)
Објаснување на вториот тест пример: Играта подморница се игра во матрица со димензии 3x3. Има 2 места каде подморницата е поставена вертикално (подморницата е матрица со димензии 2x1). Има 3 места каде подморницата е поставена хоризонтално (подморницата е матрица со димензии 1x2).