En cierta población del Estado de México no existen escuelas, sin embargo, debido al crecimiento económico del lugar el presidente municipal consiguió presupuesto para construir la escuela pero tiene dudas de donde construirla.

El municipio está representado por un área rectangular con un tamaño que va desde 1x1 hasta 500 x 500 existe la posibilidad de construir la escuela en alguna celda que no esté ocupada por alguna vivienda o por el río, el presidente municipal quiere, que en donde se construya la escuela sea el lugar en donde los alumnos tengan que caminar la menor distancia.

Dentro del mapa del municipio hay celdas que contienen valores positivos "j" que van desde 1 hasta 50 este número indica que existe una vivienda (que puede ser una casa o un edificio) en donde viven una cantidad "j" de alumnos. Un alumno solo se puede mover a una celda adyacente vertical u horizontalmente y no puede atravesar alguna casa ni el río. La distancia que el alumno camina es igual a la cantidad de pasos que debe ir desde su vivienda hasta el lugar donde se colocará la escuela.

PROBLEMA

Deberás escribir un programa ayude encontrar al presidente municipal el mejor lugar para construir la escuela, esto es, que la suma de los pasos de todos los alumnos a la escuela sea el mínimo posible.

DESCRIPCION DE LA ENTRADA

• En la primera línea 2 valores enteros "r" (renglones) y "c" (columnas) en el rango de 1 <= r,c <= 500 que representan la cantidad de renglones y columnas que conforman el municipio.
• En la segunda línea un valor entero "nv" 1<= nv <= 50 que representa en total de viviendas en el municipio
• En la siguiente nv líneas 3 números "ri","ci" y "vi" que representan el renglón y columna donde se encuentra la vivienda "i" y el valor "vi" 1 <= vi <= 50 que representa la cantidad de jóvenes que asistirán a la escuela de esa vivienda.
• En la siguiente línea un valor "nr" en el rango de 1 <= nr <= 200 que son las coordenadas dentro del municipio ocupado por el río.
• En la siguientes "nr" líneas 2 números "ri" y "ci" las coordenadas de la celdas que cubre el rio primero va el renglón y después la columna
• El área rectangular tiene su posición inicial (1,1) en la esquina superior izquierda y la posición r,c en la esquina inferior derecha.

DESCRIPCION DE LA SALIDA

• En el primero renglón va la cantidad mínima de pasos que darán todos los alumnos que irán a la escuela.
• En la segunda línea irán las coordenadas de la celda donde se debe construir la escuela, en caso de existir más de una celda donde la distancia sea mínima se deben imprimir en los siguientes renglones en orden ascendente solo los valores del renglón y columna que cumplen con el empate, primero ordenados por renglón y después por columna

Entrada

4  4
2
1  2  4
3  1   5
2
1  3
2  3

Salida

13
2   1
3   2