#include<bits/stdc++.h>
#define fi first
#define se second
#define pb(i) push_back(i)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=b;i>=a;i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define VI vector<int>
#define VLL vector<ll>
#define MPII map<pair<int,int>,int>
#define mp make_pair
#define PQI priority_queue<int>
#define lowbit(x) x&-x
#define debug(a) cout<<#a<<'='<<a<<'\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e6 + 10;
const int M = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const int inf = - INF;
const int mod = 1e9+7;
const double pi = acos(-1.0);
const double eps=1e-5;

struct point{
    int x,y;
    bool operator < (point t) const{
        if (x == t.x)
            return y < t.y;
        return x < t.x;
    }
    bool operator == (point t) const{
        return x == t.x && y == t.y;
    }
}p[N];
int a[M],c[M];
int getsum(int x){
    int res = 0;
    while(x){
        res += c[x];
        x-=lowbit(x);
    }
    return res;
}
void update(int x, int y, int n){
    while (x <= n){
        c[x] += y;
        x += lowbit(x);
    }
}
point read(){
    int x,y;
    scanf("%d%d", &x, &y);
    return (point){x,y};
}
int main()
{
    int h, w, m;
    scanf("%d%d%d", &h, &w, &m);
    int mx = h + 1, my = w + 1;
    for (int i = 1; i <= m; i++){
        p[i] = read();
        if (p[i].y == 1)
            mx = min(mx, p[i].x);
        if (p[i].x == 1)
            my = min(my, p[i].y);
    }
    for (int i = mx + 1; i <= h; i++){
        p[++m].x = i;
        p[m].y = 1;
    }
    for (int i = my + 1; i <= w; i++){
        p[++m].x = 1;
        p[m].y = i;
    }
    sort(p + 1, p + 1 + m);
    //m = unique(p + 1, p + 1 + m) -(p + 1);
    int pos = 1;
    ll ans = 0;
    for (int i = 1; i <= m; i++){
        if (a[p[i].y] == 0){
            a[p[i].y] = 1;
            update(p[i].y, 1, w);
        }
        if (i == m || p[i + 1].x != p[i].x){
            ans += getsum(w) - getsum(p[pos].y - 1);
            pos = i + 1;
        }
    }
    printf("%lld\n", 1ll* h * w - ans);
    return 0;
}
#include <cmath>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <vector>
#include <map>
#include<cstdio>
#include<functional>
#include <bitset>
#include <iomanip>
#include <cctype>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define repr(i, n) for(int i = n; i >= 0; i--)
#define ll long long
using namespace std;
template <typename T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }
template <typename T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
const ll INF = 1000000000000000000;
const ll MOD = 1e9 + 7;

vector<vector<ll>> dist;

int main()
{
	ll n; cin >> n;
	vector<ll> xl(n);
	vector<ll> yl(n);
	vector<ll> zl(n);
	dist.resize(n, vector<ll>(n));
	vector<vector<ll>> dp(1 << 17 + 1,vector<ll>(18, INF));
	rep(i, n) {
		ll x, y, z; cin >> x >> y >> z;
		xl[i] = x;
		yl[i] = y;
		zl[i] = z;
	}
	rep(i, n) {
		rep(j, n) {
			dist[i][j] = abs(xl[i] - xl[j]) + abs(yl[i] - yl[j]) + max((ll)0, zl[j] - zl[i]);
		}
	}
	dp[1][0] = 0;
	rep(i, 1 << n) {
		rep(x, n) {
			if (i & (1 << x)) {
				rep(y, n) {
					chmin(dp[i | (1 << y)][y], dp[i][x] + dist[x][y]);
				}
			}
		}
	}
	cout << dp[(1 << n) - 1][0] << endl;
	system("Pause");
}

