#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define fst first
#define snd second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
typedef long long ll;
typedef vector<int> vi;
const int MAXN = 1e5 + 2;
int n, m;
vector<pair<int,ll>> a[MAXN];
ll solve1(){
ll sum=0;
for(int i=0; i<n; i++){
for(auto& [y, w] : a[i]) sum += w;
}
return sum;
}
ll solve2(){
ll res1=0, res2=0, res3=0;
for(auto& [y, w] : a[0]) res1 += w;
for(auto& [y, w] : a[1]) res2 += w;
if(n>2){
res3=res2;
ll acc=res2;
int i=0, j=0;
for(int h=0; h<n; h++){
while(j<sz(a[1]) && a[1][j].fst<=h) acc -= a[1][j++].snd;
while(i<sz(a[0]) && a[0][i].fst<=h) acc += a[0][i++].snd;
res3=max(res3,acc);
}
}
return max(res1,max(res2,res3));
}
ll dp1[MAXN][2];
ll solve3(int i, int flag){
if(i==n) return 0;
ll& ret = dp1[i][flag];
if(ret != -1) return ret;
ret = solve3(i+1, 1);
if(sz(a[i])){
if(flag==1) ret=max(ret,a[i][0].snd+solve3(i+1,0));
if(i<n-1) ret=max(ret,a[i][0].snd+solve3(i+2,1));
}
return ret;
}
ll dp2[300][1000];
ll solve4(int i, int v){
if(i==n) return 0;
ll& ret = dp2[i][v];
if(ret != -1) return ret;
int prev_used = (v <= n) ? v : 0, curr_used = (v > n) ? v - n : 0;
int l=-1,r=-1;
ll acc=0;
for(int j=0; j<sz(a[i]); j++){
if(a[i][j].fst < curr_used) continue;
if(l==-1) l=r=j;
if(a[i][j].fst < prev_used) acc+=a[i][j].snd, r++;
else break;
}
ret = solve4(i+1, 0) + acc;
ll curr=acc;
for(int h=0; h<n; h++){
while(l<r && a[i][l].fst <= h) curr-=a[i][l++].snd;
ret=max(ret,curr+solve4(i+1, h+1));
}
if(i<n-1 && r!=-1){
for(int j=r; j<sz(a[i]); j++){
acc += a[i][j].snd;
ret=max(ret, acc+solve4(i+1, a[i][j].fst+1+n));
}
}
return ret;
}
ll max_weights(int N, int M, vi X, vi Y, vi W) {
bool subtask1=true, subtask2=true, subtask3=true, subtask4_5=n<=300;
n = N, m = M;
for(int i=0; i<m; i++){
subtask1 &= X[i] % 2 == 0;
subtask2 &= X[i] <= 1;
subtask3 &= Y[i] == 0;
a[X[i]].pb(mp(Y[i], ll(W[i])));
}
for(int i=0; i<n; i++) sort(all(a[i]));
if(subtask1) return solve1();
if(subtask2) return solve2();
if(subtask3){
memset(dp1,-1,sizeof(dp1));
return solve3(0, 0);
}
if(subtask4_5){
memset(dp2, -1, sizeof(dp2));
return solve4(0, 0);
}
return 0;
}
