是不是只有我不会网络流。

是不是只有我一个人这种题都要想 3h。

考虑把题目抽象，每种不合法方案其实都形如一个 .|. 然后左右各“接”一个点。

从图中所给范式来看，旁边所“接”的点由当前特殊边所在列与前后两个共有，在同一列内也相邻共有。

于是先对奇数行建最小割模型（文理分科模型）。

我们拆点！

不 言 而 喻。

一 目 了 然。

但是！

图中的左部点与右部点对偶数列竖线的作用是相反的。

方法是，把偶数列竖线反过来加进图的中央。

然后完了。

然而这么说可能并不清晰，具体建图请见代码。

// 想了 3h。qwq
// 还是 too young too simple。
// 并不是最大权闭合子图模型。其实用文理分科的方法就好了。

#include <algorithm>
#include <map>
#include <queue>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
namespace Dinic
{
    uint To[2000005],Last[2000005],tp;uint Flow[2000005];
    uint n,End[2000005],Cur[2000005],Dep[2000005];bol Gone[2000005];
    voi build(uint n){Dinic::n=n;tp=0;for(uint i=0;i<n;i++)End[i]=-1;}
    voi insert(uint u,uint v,uint f){To[tp]=v,Last[tp]=End[u],Flow[tp]=f,End[u]=tp++;To[tp]=u,Last[tp]=End[v],Flow[tp]=0,End[v]=tp++;}
    bol bfs(uint s,uint t)
    {
        for(uint i=0;i<n;i++)Cur[i]=End[i],Dep[i]=-1;
        Dep[s]=0;std::queue<uint>Q;Q.push(s);
        while(!Q.empty()){uint p=Q.front();Q.pop();for(uint e=End[p];~e;e=Last[e])if(Flow[e]&&_min(Dep[To[e]],Dep[p]+1))Q.push(To[e]);}
        return~Dep[t];
    }
    uint dfs(uint p,uint t,uint f)
    {
        if(Gone[p])return 0;
        if(p==t)return f;
        Gone[p]=true;
        uint ans=0;
        for(uint&e=Cur[p];~e;e=Last[e])if(Flow[e]&&Dep[To[e]]==Dep[p]+1)
        {
            uint w=dfs(To[e],t,std::min(f,Flow[e]));f-=w,ans+=w,Flow[e]-=w,Flow[e^1]+=w;if(!f)return Gone[p]=false,ans;
        }
        return Gone[p]=false,ans;
    }
    uint run(uint s,uint t)
    {
        uint ans=0;
        while(bfs(s,t))ans+=dfs(s,t,-1);
        return ans;
    }
};
std::map<std::pair<uint,uint>,uint>M;
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
#endif
    uint n;scanf("%*u%*u%u",&n);
    Dinic::build(n*2+2);
    for(uint i=0,x,y,v;i<n;i++)
    {
        scanf("%u%u%u",&x,&y,&v);
        M[{x,y}]=i;
        Dinic::insert(i<<1,i<<1|1,v);
        switch(x%4)
        {
            case 0:
                if(y&1)
                {
                    Dinic::insert(n<<1,i<<1,-1);
                    if(M.count({x+1,y}))Dinic::insert(i<<1|1,M[{x+1,y}]<<1,-1);
                    if(M.count({x,y+1}))Dinic::insert(i<<1|1,M[{x,y+1}]<<1,-1);
                    if(M.count({x,y-1}))Dinic::insert(i<<1|1,M[{x,y-1}]<<1,-1);
                }
                else
                {
                    if(M.count({x,y-1}))Dinic::insert(M[{x,y-1}]<<1|1,i<<1,-1);
                    if(M.count({x,y+1}))Dinic::insert(M[{x,y+1}]<<1|1,i<<1,-1);
                    if(M.count({x+1,y}))Dinic::insert(M[{x+1,y}]<<1|1,i<<1,-1);
                    if(M.count({x-1,y}))Dinic::insert(i<<1|1,M[{x-1,y}]<<1,-1);
                }
                break;
            case 1:
                if(y&1)
                {
                    if(M.count({x,y-1}))Dinic::insert(M[{x,y-1}]<<1|1,i<<1,-1);
                    if(M.count({x,y+1}))Dinic::insert(M[{x,y+1}]<<1|1,i<<1,-1);
                    if(M.count({x-1,y}))Dinic::insert(M[{x-1,y}]<<1|1,i<<1,-1);
                    if(M.count({x+1,y}))Dinic::insert(i<<1|1,M[{x+1,y}]<<1,-1);
                }
                else
                {
                    Dinic::insert(n<<1,i<<1,-1);
                    if(M.count({x-1,y}))Dinic::insert(i<<1|1,M[{x-1,y}]<<1,-1);
                    if(M.count({x,y+1}))Dinic::insert(i<<1|1,M[{x,y+1}]<<1,-1);
                    if(M.count({x,y-1}))Dinic::insert(i<<1|1,M[{x,y-1}]<<1,-1);
                }
                break;
            case 2:
                if(y&1)
                {
                    if(M.count({x,y-1}))Dinic::insert(i<<1|1,M[{x,y-1}]<<1,-1);
                    if(M.count({x,y+1}))Dinic::insert(i<<1|1,M[{x,y+1}]<<1,-1);
                    if(M.count({x+1,y}))Dinic::insert(i<<1|1,M[{x+1,y}]<<1,-1);
                    if(M.count({x-1,y}))Dinic::insert(M[{x-1,y}]<<1|1,i<<1,-1);
                }
                else
                {
                    Dinic::insert(i<<1|1,n<<1|1,-1);
                    if(M.count({x+1,y}))Dinic::insert(M[{x+1,y}]<<1|1,i<<1,-1);
                    if(M.count({x,y+1}))Dinic::insert(M[{x,y+1}]<<1|1,i<<1,-1);
                    if(M.count({x,y-1}))Dinic::insert(M[{x,y-1}]<<1|1,i<<1,-1);
                }
                break;
            case 3:
                if(y&1)
                {
                    Dinic::insert(i<<1|1,n<<1|1,-1);
                    if(M.count({x-1,y}))Dinic::insert(M[{x-1,y}]<<1|1,i<<1,-1);
                    if(M.count({x,y+1}))Dinic::insert(M[{x,y+1}]<<1|1,i<<1,-1);
                    if(M.count({x,y-1}))Dinic::insert(M[{x,y-1}]<<1|1,i<<1,-1);
                }
                else
                {
                    if(M.count({x,y-1}))Dinic::insert(i<<1|1,M[{x,y-1}]<<1,-1);
                    if(M.count({x,y+1}))Dinic::insert(i<<1|1,M[{x,y+1}]<<1,-1);
                    if(M.count({x-1,y}))Dinic::insert(i<<1|1,M[{x-1,y}]<<1,-1);
                    if(M.count({x+1,y}))Dinic::insert(M[{x+1,y}]<<1|1,i<<1,-1);
                }
                break;
        }
    }
    printf("%u\n",Dinic::run(n<<1,n<<1|1));
    return 0;
}