На одной далёкой-далёкой планете внимание
исследователей привлёк заброшенный храм. Основное внимание при входе в храм
привлекала прямоугольная стена, состоящая N колонн по М кирпичей
в каждой. На каждом кирпиче гордо красовалось выведенное каллиграфическим почерком
число. Учёные обнаружили, что прикосновение к кирпичу с числом приводит к его
исчезновению. Также исчезает любой кирпич, находящийся рядом с одним из
исчезнувших (сверху, снизу, слева или справа), если число на нём отличается от
числа на активированном прикосновением кирпиче не более чем на C.
Процесс продолжается лавинообразно, останавливаясь на кирпичах с числами,
отличающимися более чем на C от
числа на начальном кирпиче. После исчезновения группы кирпичей оставшиеся без
опоры кирпичи падают вертикально вниз. В случае исчезновения всех кирпичей
одной колонны после вертикального падения происходит сдвиг влево всех колонн,
находившихся правее исчезнувшей.
Учёные пришли к выводу, что процесс уничтожения
культурной ценности пора прекратить. Но до этого необходимо найти, сколько
кирпичей осталось в стене после выполненных исследователями нажатий.
В первой строке входного файла содержатся 3 числа: N
— количество колонн, M — начальное
количество кирпичей в каждой колонне (1 <= N, M <= 50) и C — разность
чисел, поддерживающая волну исчезновений кирпичей (0 <= C <= 100).
Далее идут N строк по M
чисел — числа на кирпичах до прикосновений. Вертикальная колонна описана во
входных данных горизонтально. Низ колонны соответствует началу строки, верх —
концу. Самая левая колонна описана в первой из N строк,
самая правая в последней.
Затем идёт число K — количество
прикосновений учёных (0 <= K <= 1000).
Далее в K строках даны координаты активированных кирпичей X
— номер колонны слева (1 <= X <= N), затем Y
— номер ряда снизу (1 <= Y <= M).
Гарантируется, что все нажатия корректны, то есть
кирпич с такими координатами во время нажатия существовал.
Выведите в выходной файл одно число — количество кирпичей,
оставшихся в стене.
Пример
|
ввод
|
Вывод
|
|
4
5 1
1
1 3 1 2
3
3 3 3 1
1
5 5 5 1
1
1 4 1 1
3
1
1
1
1
1
1
|
7
|
