Вы добываете минералы на далёкой планете. Минералы расположены на поле N х M клеточек. Для каждой клеточки поля известно, сколько в ней содержится минералов (целое неотрицательное число).
На поле стоят добывалки, которые могут добывать минералы на расстоянии D от себя. Расстояние D выражается в клеточках по горизонтали, вертикали и диагонали (см. пример на картинке ниже.) Система координат начинается в левом верхнем углу, координаты X и Y отсчитываются от нуля, ось OX направлена вправо, ось OY направлена вниз (экранная система координат).
Требуется определить, сколько всего минералов будет добыто при заданной расстановке добывалок.
Формат ввода В первой строке целые числа N и M - размеры поля по X и Y. Размеры в пределах от 1 до 1024. Далее M строк, в каждой по N чисел через пробел - количества минералов для всех клеток поля. Строка ввода - строка поля по направлению X. Строки расположены по возрастанию координаты Y. В следующей строке K - количество добывалок. Далее K строк, в каждой через пробел 3 целых числа - X, Y, D очередной добывалки. X и Y - координаты. D - расстояние, на котором она работает. Координаты X и Y отсчитываются от нуля. Гарантируется, что они попадают в поле. Т.е. 0 ⇐ X_i ⇐ N - 1, 0 ⇐ Y_i ⇐ M - 1.
Формат вывода Одно целое число - количество добытых минералов.
| Ввод | Результат |
|---|---|
| 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 4 4 2 | 17 |