#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
using namespace std;
typedef long long LL;
typedef long double LD;
typedef complex<LD> CMP;
class TheMountain { public:
int minSum(int H, int W, vector <int> Y, vector <int> X, vector <int> V)
{
const int N = Y.size();
static const int INF = 0x3fffffff;
int best = INF;
vector< vector<int> > fixed(H, vector<int>(W, 0));
for(int i=0; i<N; ++i)
fixed[Y[i]][X[i]] = V[i];
for(int x=0; x<W; ++x)
{
vector< vector<int> > td(H, vector<int>(W));
vector<int> td_sum(H);
int td_end = 0;
for(int y=0; y<H; ++y)
{
for(int a=0; a<x; ++a) {
int req = 1;
if(0<=a-1&&a-1<W) req = max(req, td[y][a-1]+1);
if(0<=y-1&&y-1<H) req = max(req, td[y-1][a]+1);
if(fixed[y][a]) {
if(fixed[y][a] < req)
goto label_td_end;
td[y][a] = fixed[y][a];
} else {
td[y][a] = req;
}
}
for(int a=W-1; a>x; --a) {
int req = 1;
if(0<=a+1&&a+1<W) req = max(req, td[y][a+1]+1);
if(0<=y-1&&y-1<H) req = max(req, td[y-1][a]+1);
if(fixed[y][a]) {
if(fixed[y][a] < req)
goto label_td_end;
td[y][a] = fixed[y][a];
} else {
td[y][a] = req;
}
}
int a = x;
{
int req = 1;
if(0<=a-1&&a-1<W) req = max(req, td[y][a-1]+1);
if(0<=a+1&&a+1<W) req = max(req, td[y][a+1]+1);
if(0<=y-1&&y-1<H) req = max(req, td[y-1][a]+1);
if(fixed[y][a]) {
if(fixed[y][a] < req)
goto label_td_end;
td[y][a] = fixed[y][a];
} else {
td[y][a] = req;
}
}
td_sum[y] = accumulate(td[y].begin(), td[y].end(), 0);
td_end ++;
}
label_td_end:;
vector< vector<int> > bu(H, vector<int>(W));
vector<int> bu_sum(H);
int bu_begin = H;
for(int y=H-1; y>=0; --y)
{
for(int a=0; a<x; ++a) {
int req = 1;
if(0<=a-1&&a-1<W) req = max(req, bu[y][a-1]+1);
if(0<=y+1&&y+1<H) req = max(req, bu[y+1][a]+1);
if(fixed[y][a]) {
if(fixed[y][a] < req)
goto label_bu_end;
bu[y][a] = fixed[y][a];
} else {
bu[y][a] = req;
}
}
for(int a=W-1; a>x; --a) {
int req = 1;
if(0<=a+1&&a+1<W) req = max(req, bu[y][a+1]+1);
if(0<=y+1&&y+1<H) req = max(req, bu[y+1][a]+1);
if(fixed[y][a]) {
if(fixed[y][a] < req)
goto label_bu_end;
bu[y][a] = fixed[y][a];
} else {
bu[y][a] = req;
}
}
int a = x;
{
int req = 1;
if(0<=a-1&&a-1<W) req = max(req, bu[y][a-1]+1);
if(0<=a+1&&a+1<W) req = max(req, bu[y][a+1]+1);
if(0<=y+1&&y+1<H) req = max(req, bu[y+1][a]+1);
if(fixed[y][a]) {
if(fixed[y][a] < req)
goto label_bu_end;
bu[y][a] = fixed[y][a];
} else {
bu[y][a] = req;
}
}
bu_sum[y] = accumulate(bu[y].begin(), bu[y].end(), 0);
bu_begin --;
}
label_bu_end:;
if(td_end <= bu_begin)
continue;
int baseline = 0;
for(int Y=0; Y<H; ++Y)
baseline += (Y<bu_begin ? td_sum[Y] : Y==bu_begin ? 0 : bu_sum[Y]);
for(int y=bu_begin; y<td_end; ++y)
{
int score = baseline;
for(int x=0; x<W; ++x)
score += max(td[y][x], bu[y][x]);
best = min(best, score);
if(y<H)
baseline += td_sum[y] - bu_sum[y+1];
}
}
return (best==INF ? -1 : best);
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, TheMountain().minSum(n, m, rowIndex, columnIndex, element));}
int main(){
CASE(0)
int n = 2;
int m = 3;
int rowIndex_[] = {0, 0, 0, 1, 1, 1};
vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*rowIndex_));
int columnIndex_[] = {0, 1, 2, 0, 1, 2};
vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex_)/sizeof(*columnIndex_));
int element_[] = {4, 6, 9, 1, 3, 6};
vector <int> element(element_, element_+sizeof(element_)/sizeof(*element_));
int _ = 29;
END
CASE(1)
int n = 2;
int m = 3;
int rowIndex_[] = {1, 0, 1};
vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*rowIndex_));
int columnIndex_[] = {2, 2, 0};
vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex_)/sizeof(*columnIndex_));
int element_[] = {5, 7, 6};
vector <int> element(element_, element_+sizeof(element_)/sizeof(*element_));
int _ = 40;
END
CASE(2)
int n = 3;
int m = 3;
int rowIndex_[] = {0, 0, 2, 2};
vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*rowIndex_));
int columnIndex_[] = {0, 2, 2, 0};
vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex_)/sizeof(*columnIndex_));
int element_[] = {1, 1, 1, 1};
vector <int> element(element_, element_+sizeof(element_)/sizeof(*element_));
int _ = 15;
END
CASE(3)
int n = 2;
int m = 2;
int rowIndex_[] = {0, 0, 1, 1};
vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*rowIndex_));
int columnIndex_[] = {0, 1, 1, 0};
vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex_)/sizeof(*columnIndex_));
int element_[] = {5, 8, 5, 8};
vector <int> element(element_, element_+sizeof(element_)/sizeof(*element_));
int _ = -1;
END
CASE(4)
int n = 1;
int m = 3;
int rowIndex_[] = {0};
vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*rowIndex_));
int columnIndex_[] = {1};
vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex_)/sizeof(*columnIndex_));
int element_[] = {1};
vector <int> element(element_, element_+sizeof(element_)/sizeof(*element_));
int _ = -1;
END
CASE(5)
int n = 123;
int m = 45;
int rowIndex_[] = {2, 3, 5, 7, 11};
vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*rowIndex_));
int columnIndex_[] = {13, 17, 19, 23, 29};
vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex_)/sizeof(*columnIndex_));
int element_[] = {100, 200, 300, 400, 500};
vector <int> element(element_, element_+sizeof(element_)/sizeof(*element_));
int _ = 367047;
END
CASE(6)
int n = 200;
int m = 200;
int rowIndex_[] = {5};
vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*rowIndex_));
int columnIndex_[] = {8};
vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex_)/sizeof(*columnIndex_));
int element_[] = {666};
vector <int> element(element_, element_+sizeof(element_)/sizeof(*element_));
int _ = 5737554;
END
CASE(7)
int n = 10;
int m = 10;
int rowIndex_[] = {0, 8, 7};
vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*rowIndex_));
int columnIndex_[] = {3, 1, 9};
vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex_)/sizeof(*columnIndex_));
int element_[] = {5, 4, 7};
vector <int> element(element_, element_+sizeof(element_)/sizeof(*element_));
int _ = 593;
END
CASE(8)
int n = 200;
int m = 200;
int rowIndex_[] = {129,99,142,33,111,174,169,176,83,143,70,116,193,139,7,35,111,4,189,111,170,29,16,87,115,4,60,71,37,138,128,38,61,176,187,66,64,84,120,104,124,129,91,137,114,187,97,115,151,140};
vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*rowIndex_));
int columnIndex_[] = {191,148,194,13,90,17,185,163,17,170,193,165,140,158,85,15,56,91,9,68,153,83,9,97,74,40,160,165,49,151,173,98,123,44,139,164,66,112,141,172,91,147,71,167,123,53,189,86,71,171};
vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex_)/sizeof(*columnIndex_));
int element_[] = {953,216,307,197,970,590,659,153,79,262,628,153,106,904,888,249,224,839,29,327,664,619,387,325,865,849,516,313,649,135,713,585,347,279,702,837,682,817,844,981,401,410,982,891,167,102,646,73,784,455};
vector <int> element(element_, element_+sizeof(element_)/sizeof(*element_));
int _ = -1;
END
/*
CASE(9)
int n = ;
int m = ;
int rowIndex_[] = ;
vector <int> rowIndex(rowIndex_, rowIndex_+sizeof(rowIndex_)/sizeof(*rowIndex_));
int columnIndex_[] = ;
vector <int> columnIndex(columnIndex_, columnIndex_+sizeof(columnIndex_)/sizeof(*columnIndex_));
int element_[] = ;
vector <int> element(element_, element_+sizeof(element_)/sizeof(*element_));
int _ = ;
END
*/
}
// END CUT HERE