Record du monde – Épreuve régionale 2018

Énoncé¶

Aujourd'hui c'est le grand jour ! Après des mois de préparations, il est enfin temps pour Joseph de cuisiner la plus grande crêpe jamais conçue et ainsi établir le nouveau record du monde.

Pour venir à bout d'une telle tâche, Joseph a construit une poêle rectangulaire gigantesque. Le problème est de distribuer équitablement la chaleur, pour que la pâte cuise le plus uniformément possible. Différentes plaques de cuisson sont alors installées à des endroits bien précis sous la poêle, mais Joseph aimerait s'assurer qu'aucun emplacement ne dépasse une certaine quantité de chaleur, sans quoi une partie de la crêpe brûlerait !

La poêle sera représentée sous la forme d'une grille rectangulaire de dimensions $N$x$M$. Toutes les cases ont initialement une chaleur de 0. Chaque plaque de cuisson est placée sous une case ($x_i$ ; $y_i$) et émet une quantité de chaleur $q_i$. Comme chacun le sait, la chaleur se diffuse aux alentours, et diminue d'intensité au fur et à mesure. Voici un exemple de diffusion de la chaleur sur les cases voisines :

De plus, lorsqu'une case est chauffée par plusieurs plaques, les quantités de chaleurs s'additionnent :

Aidez Joseph à déterminer la case de la poêle dont la quantité de chaleur est maximale.

Entrée¶

Sur la première ligne, deux entiers représentant les dimensions rectangulaires de la poêle. La ligne d'après contient un entier $T$ indiquant le nombre de plaques de cuisson utilisées par Joseph.

$T$ lignes suivent, contenant chacune trois entiers : $x_i$, $y_i$ et $q_i$ qui signifie qu'une plaque de cuisson est placée sous la case ($x_i$ ; $y_i$) avec pour quantité de chaleur $q_i$.

Sortie¶

Un unique entier représentant la quantité de chaleur maximale atteinte dans les conditions de l'entrée.

Contraintes¶

• $1 \le N \le 100$
• $1 \le M \le 100$
• $1 \le T \le 100$
• $0 \le x_i \lt N$
• $0 \le y_i \lt M$
• $1 \le q_i \le 50$