#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
const int MAXN = 300100;
int n, w[MAXN], m;
pii a[MAXN];
namespace A{
ll solve(){
ll ans = 0;
for(int i=1; i<=m; i++){
ans += w[i];
}
return ans;
}
}
namespace B{
ll d[3001][3001];
ll dp[3001][3001];
ll pref[3001][3001];
ll ddp[3001][3001];
ll suf[3001];
ll solve(){
for(int i=1; i<=m; i++){
d[a[i].ff][a[i].ss] += w[i];
}
for(int i=1; i<=n; i++){
dp[0][i] = -1e18;
ddp[0][i] = -1e18;
}
dp[0][0] = 0;
ddp[0][0] = 0;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
pref[i][j] = pref[i][j - 1] + d[i][j];
}
ll mx = -1e18;
for(int j=n; j>=0; j--){
mx = max(mx, dp[i-1][j] + pref[i][j]);
suf[j] = mx;
}
ll pddp = -1e18, pdp = -1e18;
mx = -1e18;
for(int j=0; j<=n; j++) mx = max(mx, dp[i-1][j]);
for(int j=0; j<=n; j++){
ddp[i][j] = mx;
dp[i][j] = 0;
pddp = max(pddp, ddp[i-1][j]-pref[i-1][j]);
ddp[i][j] = max(ddp[i][j], pddp + pref[i-1][j]);
dp[i][j] = ddp[i][j];
dp[i][j] = max(dp[i][j], suf[j]-pref[i][j]);
pdp = max(pdp, ddp[i-1][j]-pref[i-1][j]);
dp[i][j] = max(dp[i][j], pdp+pref[i-1][j]);
}
}
//for(int i=1; i<=n; i++){
// for(int j=0; j<=n; j++){
// cout<<dp[i][j]<<' ';
// }
// cout<<'\n';
//}
ll ans = 0;
for(int i=0; i<=n; i++) ans = max(ans, dp[n][i]);
return ans;
}
}
namespace C{
ll d[5][100100];
ll dp[5][100100];
ll pref[5][100100];
ll ddp[5][100100];
ll suf[100100];
ll solve(){
for(int i=1; i<=m; i++){
d[a[i].ff][a[i].ss] += w[i];
}
for(int i=1; i<=n; i++){
dp[0][i] = -1e18;
ddp[0][i] = -1e18;
}
dp[0][0] = 0;
ddp[0][0] = 0;
for(int i=1; i<=3; i++){
for(int j=1; j<=n; j++){
pref[i][j] = pref[i][j - 1] + d[i][j];
}
ll mx = -1e18;
for(int j=n; j>=0; j--){
mx = max(mx, dp[i-1][j] + pref[i][j]);
suf[j] = mx;
}
ll pddp = -1e18, pdp = -1e18;
mx = -1e18;
for(int j=0; j<=n; j++) mx = max(mx, dp[i-1][j]);
for(int j=0; j<=n; j++){
ddp[i][j] = mx;
dp[i][j] = 0;
pddp = max(pddp, ddp[i-1][j]-pref[i-1][j]);
ddp[i][j] = max(ddp[i][j], pddp + pref[i-1][j]);
dp[i][j] = ddp[i][j];
dp[i][j] = max(dp[i][j], suf[j]-pref[i][j]);
pdp = max(pdp, ddp[i-1][j]-pref[i-1][j]);
dp[i][j] = max(dp[i][j], pdp+pref[i-1][j]);
}
}
//for(int i=1; i<=n; i++){
// for(int j=0; j<=n; j++){
// cout<<dp[i][j]<<' ';
// }
// cout<<'\n';
//}
ll ans = 0;
for(int i=0; i<=n; i++) ans = max(ans, dp[3][i]);
return ans;
}
}
namespace D{
ll d[100100][10];
ll dp[100100][10];
ll pref[100100][10];
ll ddp[100100][10];
ll suf[10];
ll solve(){
for(int i=1; i<=m; i++){
d[a[i].ff][a[i].ss] += w[i];
}
for(int i=1; i<=5; i++){
dp[0][i] = -1e18;
ddp[0][i] = -1e18;
}
dp[0][0] = 0;
ddp[0][0] = 0;
for(int i=1; i<=n; i++){
for(int j=1; j<=5; j++){
pref[i][j] = pref[i][j - 1] + d[i][j];
}
ll mx = -1e18;
for(int j=5; j>=0; j--){
mx = max(mx, dp[i-1][j] + pref[i][j]);
suf[j] = mx;
}
ll pddp = -1e18, pdp = -1e18;
mx = -1e18;
for(int j=0; j<=5; j++) mx = max(mx, dp[i-1][j]);
for(int j=0; j<=5; j++){
ddp[i][j] = mx;
dp[i][j] = 0;
pddp = max(pddp, ddp[i-1][j]-pref[i-1][j]);
ddp[i][j] = max(ddp[i][j], pddp + pref[i-1][j]);
dp[i][j] = ddp[i][j];
dp[i][j] = max(dp[i][j], suf[j]-pref[i][j]);
pdp = max(pdp, ddp[i-1][j]-pref[i-1][j]);
dp[i][j] = max(dp[i][j], pdp+pref[i-1][j]);
}
}
//for(int i=1; i<=n; i++){
// for(int j=0; j<=n; j++){
// cout<<dp[i][j]<<' ';
// }
// cout<<'\n';
//}
ll ans = 0;
for(int i=0; i<=5; i++) ans = max(ans, dp[n][i]);
return ans;
}
}
long long max_weights(int N, int M, vector<int> X, vector<int> Y,
vector<int> W) {
n = N;
m = M;
for(int i=1; i<=m; i++){
a[i] = {X[i-1]+1, Y[i-1]+1};
}
for(int i=1; i<=m; i++){
w[i] = W[i-1];
}
int ok1 = 1;
int ok2 = 1, ok3 = 1;
for(int i=1; i<=m; i++){
ok1 &= (a[i].ff % 2 == 1);
ok2 &= (a[i].ff <= 2);
ok3 &= (a[i].ss == 1);
}
if(ok1) return A::solve();
if(n <= 3000) return B::solve();
if(ok2) return C::solve();
if(ok3) return D::solve();
return 0;
}
