Reconnaissance d'ovnis – Regional event 2012

Level 6

Énoncé

Lorsqu'on regarde le ciel, on peut parfois apercevoir un amas de disparités négatives et positives. Le potentiel d'une zone est égal à la somme des énergies s'y trouvant. C'est dans des zones de fort potentiel que l'on décèle parfois des ovnis.

La « zone de ciel » dans laquelle nous cherchons les ovnis est toujours rectangulaire.

On vous demande de déceler le plus fort potentiel présent dans une zone du ciel. Cette zone peut être vide.

Entrée

  • Sur la première ligne, la hauteur N de la carte.
  • Sur la deuxième ligne, la longueur M de la carte.
  • Sur les N lignes suivantes, M nombres représentant les énergies.

Sortie

Le plus fort potentiel que l'on puisse trouver dans une zone de la carte.

Contraintes

  • 1 <= N <= 100
  • 1 <= M <= 1 000

Runtime constraints

Maximum memory usage
500 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
3
4
-2 1 -1 4
2 -3 5 -7
-3 8 -1 1
Sample output
9

Submit your solution

You have to register or log in to be able to submit your solution.