Gege la grenouille – Épreuve régionale 2008

ENONCE

Gégé la grenouille est très gloutonne. Elle vit dans un marais (représenté par une grille en deux dimensions), et chaque matin, ses informateurs (de leurs noms, Gaga et Gigi) lui donnent un plan du marais, avec la quantité de nourriture disponible sur chaque case.

Le but de Gégé va être d'ingurgiter le plus de nourriture possible, en se déplaçant de cases en cases dans son marais. Dès que Gégé est sur une case, elle ingurgite toute la nourriture disponible sur cette case. En temps normal, Gégé peut se déplacer d'une case à partir de la case où elle est, que ce soit horizontalement, verticalement ou en diagonale (bien sûr, sans sortir du marais). Mais certaines cases du marais sont magiques, et dès que Gégé tombe sur une telle case, elle peut se déplacer K fois (K est donné en entrée) sans limitation de nombre de cases (toujours horizontalement, verticalement ou en diagonale).

Autre caractéristique importante du déplacement de Gégé : elle ne peut aller que sur des cases dont la quantité de nourriture disponible (initiale) est strictement supérieure a la quantite de nourriture initiale de la case courante de Gege. (Autrement dit, Gege veut manger de plus en plus, elle est tres gloutonne). Entre autres choses, cela implique que Gégé ne peut jamais revenir sur des cases par où elle est déjà passée.

Ecrivez un programme pour aider Gégé à determiner la quantité maximale de nourriture qu'elle peut ingérer (elle est très très gloutonne !), en connaissant sa position initiale, la quantité de nourriture disponible sur chaque case, la position des cases magiques, et le paramètre K.

ENTREE

• Sur la première ligne : un nombre N (1\<=N\<=50) : les dimensions de la grille représentant le marais, et le nombre K (1 \<= K \<= 10). Ces deux entiers seront séparés d'un espace.

• Sur les N lignes suivantes, N entiers, représentant la quantité de nourriture disponible sur chaque case. (ces nombres seront entre 0 et 100)

• Sur une ligne : le nombre M de cases magiques. (1 \<= M \<= N*N)

• Sur les M lignes suivantes : deux entiers, séparés par un espace, indiquant respectivement la ligne et la colonne d'une case magique.

• Sur la dernière ligne, deux entiers, séparés par un espace, indiquant respectivement la ligne et la colonne de la case de départ de Gégé la grenouille.

Note : toutes les coordonnées du problème commencent à 0, et seront valides. Gégé mange la nourriture disponible sur sa case de départ.

SORTIE

Un entier, la quantité maximale de nourriture que peut ingérer Gégé, si elle se débrouille au mieux.

Note : La position finale de Gégé peut être quelconque ; Gégé dispose de son hélicoptère personnel.