Votre société a détecté un gros gisement de cuivre et a décidé de créer une mine à ciel ouvert. Après avoir sondé le sol, les experts de votre entreprise ont dressé une grille décrivant la zone. Chaque ligne de cette grille correspond à une couche horizontale de minerai (la première ligne correspond à la couche la moins profonde, la dernière ligne à la plus profonde) et chacune des cases de cette grille contient un entier correspondant à la valeur de revient du minerai se trouvant à cette case. Notez que la valeur de revient inclut les divers coûts d'extraction du cuivre, donc que la valeur de revient du minerai d'une case peut être négative.

La construction de la mine se fait en creusant progressivement dans le sol, par paliers. Un palier est un ensemble de cases consécutives d'une même ligne, que la société creuse pour remporter la somme des valeurs de revient des cases le composant. Créer un nouveau palier induit un coût d'installation fixe P, du fait de la mise en place de rampes d'accès, entre autres. Un palier peut être creusé seulement si les cases qui le composent sont sur la première ligne ou sont toutes sous des cases déjà creusées.

Le profit de l'opération est la somme des valeurs de revient des cases creusées diminuée du coût d'installation des paliers (égal au nombre de paliers multiplié par P). Votre objectif est d'écrire un programme qui détermine le meilleur profit qu'il est possible de réaliser.

Les tests sont répartis en cinq groupes ayant des contraintes différentes, et correspondant chacun à un score de 20 points. Dans ce qui suit, L et C représentent respectivement le nombre de lignes et de colonnes de la grille.

• Groupe A : 1 <= L, C <= 10
• Groupe B : 1 <= L, C <= 50
• Groupe C : 1 <= L <= 50 et 1 <= C <= 500
• Groupe D : 1 <= L <= 500 et 1 <= C <= 50
• Groupe E : 1 <= L, C <= 500

De plus, pour l'ensemble des tests, on a :

• -100 <= R <= 100, où R est la valeur de revient d'une case de la grille,
• 1 <= P <= 100, où P est le coût fixe de création d'un palier.

La première ligne de l'entrée contient trois entiers séparés par des espaces : L, C et P.

Chacune des L lignes suivantes contient C entiers décrivant les valeurs de revient des cases de minerai de la couche correspondante.

Votre programme doit afficher un unique entier : le meilleur profit qu'il est possible de réaliser.

4 7 10
-50 21 -1 -83 27 3 4
2 -10 60 6 11 -20 -27
-12 100 -2 2 9 -12 80
9 -21 -99 1 10 7 -8

198

Le profit maximal que l'on puisse faire est 198.

Voici une configuration avec 7 paliers (chacun identifié par un motif et une couleur) correspondant à ce maximum :

La somme des valeurs de revient des cases creusées est 268, tandis que le coût de la mise en place des paliers est de 7*10 = 70, d'où un profit de 198.