À Zagreb, la capitale de la Croatie, il a été décidé de construire un grand centre commercial en banlieue à l'occasion de l'organisation de l'IOI 2007. Le site candidat pour la construction du centre commercial est divisé en une grille de $m$ blocs horizontalement sur $n$ blocs verticalement, comme le montre la figure ci-dessous.

La ville de Zagreb a décidé de choisir une zone rectangulaire de $a$ blocs horizontalement sur $b$ blocs verticalement au sein du site candidat et d'y construire le centre commercial. Cependant, certains blocs du site candidat sont déjà habités et il est impossible de construire le centre commercial sur ces terrains. S'il n'y a aucun bloc habité à l'intérieur d'une zone rectangulaire de $a$ blocs horizontalement sur $b$ blocs verticalement, le centre commercial peut être construit en achetant tous les blocs situés dans cette zone rectangulaire.

Pour des raisons financières propres à la ville de Zagreb, le coût d'acquisition des terrains doit être réduit autant que possible. Afin d'établir un projet de budget, il est urgent de calculer le coût nécessaire à l'acquisition des terrains pour la construction du centre commercial. C'est pourquoi la ville de Zagreb a décidé de vous demander, en tant que candidat pour représenter votre pays à l'IOI 2007, d'écrire un programme à cet effet.

Écrivez un programme qui, étant donné en entrée la taille du site candidat, la taille du centre commercial, ainsi que pour chaque bloc l'information indiquant s'il est habité et, s'il ne l'est pas, le coût nécessaire pour acheter ce bloc, détermine le coût minimal d'acquisition des terrains nécessaire pour construire le centre commercial.

Dans ce qui suit, le bloc situé dans la $i$-ième colonne en partant de la gauche et la $j$-ième ligne en partant du haut du site candidat est noté $(i, j)$.

Entrée

La première ligne du fichier d'entrée mall.in contient deux entiers $m, n$ ($1 \le m, n \le 1000$) séparés par un espace. Cela indique que la taille du site candidat est de $m$ blocs horizontalement sur $n$ blocs verticalement.

La deuxième ligne contient deux entiers $a, b$ ($1 \le a, b \le 1000$) séparés par un espace. Cela indique que la taille du centre commercial est de $a$ blocs horizontalement sur $b$ blocs verticalement.

Les $n$ lignes suivantes (de la ligne $3$ à la ligne $n + 2$) contiennent les informations sur chaque bloc du site candidat. La ligne $j + 2$ ($1 \le j \le n$) représente les informations des blocs de la $j$-ième ligne en partant du haut et contient $m$ entiers $c_{1,j}, \dots, c_{m,j}$ ($-1 \le c_{i,j} \le 100$) séparés par des espaces. Lorsque $c_{i,j} = -1$, cela indique que le bloc $(i, j)$ est habité. Sinon, cela indique que le coût nécessaire pour acheter le bloc $(i, j)$ est $c_{i,j}$.

Notez que pour les données d'entrée utilisées lors de l'évaluation, la construction du centre commercial est toujours possible.

Sortie

La sortie doit être écrite sur la sortie standard. Affichez le coût minimal d'acquisition des terrains nécessaire à la construction du centre commercial.

Exemple

Entrée 1

7 6
3 2
26 29 84 15 -1 1 71
45 14 38 91 62 77 35
68 -1 -1 90 63 56 70
31 2 4 74 72 41 90
100 26 21 -1 44 72 60
71 4 40 93 48 -1 50

Sortie 1

184

Le terrain de construction du centre commercial dans cet exemple d'entrée/sortie est illustré ci-dessous. Un bloc marqué d'un $\times$ signifie qu'il est déjà habité.

Remarque

Faites attention à la taille des données d'entrée. En particulier, comme iostream en C++ est lent, il est conseillé d'utiliser fscanf ou des fonctions similaires selon les besoins.