#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pii pair<int,int>
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define pb push_back
#define sz(x) (int)(x).size()
#define rsz resize
#define ass assign
#define F(i,l,r) for(int i=(l);i<(r);++i)
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
template<typename T> using pqg = priority_queue<T, vector<T>, greater<T>>;
#define each(a,x) for(auto a:x)
#define FOR(i,a) for(int i=0;i<(a);i++)
#define ROF(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define eb emplace_back
#define ft front()
#define V vector
#include "fish.h"
ll max_weights(int n,int m,V<int> x,V<int> y,V<int> w){
bool even=1;
FOR(i,m){
if(x[i]&1){
even=0;
break;
}
}
if(even){
ll tot=0;
each(v,w)tot+=(ll)v;
return tot;
}
bool sub2=1;
FOR(i,m){
if(x[i]>1){
sub2=0;
break;
}
}
if(sub2){
V<ll> sumcol0(n+1,0),sumcol1(n+1,0);
FOR(i,m){
if(!x[i])sumcol0[y[i]+1]+=w[i];
else sumcol1[y[i]+1]+=w[i];
}
F(h,1,n+1){
sumcol0[h]+=sumcol0[h-1];
sumcol1[h]+=sumcol1[h-1];
}
ll mx=0;
FOR(h,n+1){
mx=max(mx,sumcol0[h]+(sumcol1[n]-sumcol1[h]));
mx=max(mx,sumcol1[n]);
}
return mx;
}
bool sub3=1;
FOR(i,m){
if(y[i]!=0){
sub3=0;
break;
}
}
if(sub3){
V<ll> at(n,0);
FOR(i,m)at[x[i]]=w[i];
const ll inf=1e18;
V<V<ll>> dp(2,V<ll>(2,-inf));
dp[0][0]=0;
FOR(i,n){
V<V<ll>> ndp(2,V<ll>(2,-inf));
FOR(prev,2){
FOR(cur,2){
if(dp[cur][prev]<-inf/2)continue;
FOR(nxt,2){
ll score=dp[cur][prev];
if(!cur && (prev==1 || nxt==1))score+=at[i];
ndp[nxt][cur]=max(score,ndp[nxt][cur]);
}
}
}
dp=ndp;
}
return max(dp[0][0],dp[0][1]);
}
return 0;
}
