#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include using namespace std; #define rep(i,n) for(ll i=0;i=l;i--) using ll = long long; using ld = long double; const ll mod=998244353; #define vout(v) for(auto i :v) cout< #define pb push_back #define vc vector #define vb vector #define uniq(x) sort((x).begin(),(x).end());(x).erase(unique((x).begin(),(x).end()),(x).end()) #define eb emplace_back void no(void) { cout<<"No"< dx={-1,0,1,0,1,1,-1,-1}; vector dy={0,-1,0,1,-1,1,-1,1}; bool isin(ll i,ll j,ll h,ll w) { if(i<0 || i>=h || j<0 || j>=w) return false; return true; } template bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;} template bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;} templateT vecmax(const vector&v){return *max_element(all(v));} templateT vecmin(const vector&v){return *min_element(all(v));} ll safemod(ll num,ll rule) { return (num%rule+rule)%rule; } ll sum(vector &a) { return accumulate(all(a),0ll); } templatevoid vvpr(vector> g) { rep(i,g.size()) { cout<<"here: i="<0) { if (po&1) ret=(ret*fl)%ll(MOD); fl=(fl*fl)%ll(MOD); po>>=1; } } else { while (po>0) { if(po&1) ret*=fl; fl*=fl; po>>=1; } } return ret; } bool pasolve(ll h,ll w,ll h1,ll w1) { //if(h==h1 && w==w1) return false; return (h==h1 || w==w1 || h+w==h1+w1 || h-w==h1-w1); } int main() { ll h,w,sx,sy,n; cin>>h>>w>>sx>>sy>>n; //2ta-nでいけるはず vl x(n),y(n),c(n); rep(i,n) cin>>x[i]>>y[i]>>c[i]; ll score=0; vector> dp(n+1,{(ll)-1e16,(ll)-1e16}); dp[0][0]=0; if(pasolve(sx,sy,x[0],y[0])) dp[0][1]=0; srep(i,1,n) { if(i