#include<bits/stdc++.h>
using namespace std;
long long group1(vector <int> W)
{
long long sum = 0;
for(int i : W)
{
sum += i;
}
return sum;
}
long long group2(int N, int M, vector <int> X, vector <int> Y, vector <int> W)
{
long long pref[2][N], cord = -1, mx = 0;
for(int i = 0; i < 2; i++)
{
for(int j = 0; j < N; j++)
{
pref[i][j] = 0;;
}
}
for(int i = 0; i < M; i++)
{
pref[X[i]][Y[i]] = W[i];
}
for(int i = 0; i < 2; i++)
{
for(int j = 1; j < N; j++)
{
pref[i][j] += pref[i][j - 1];
}
}
for(int i = 0; i < N; i++)
{
if(pref[0][i] - pref[1][i] > mx)
{
mx = pref[0][i] - pref[1][i];
cord = i;
}
}
long long sum = pref[1][N - 1];
if(cord >= 0)
{
sum = sum - pref[1][cord] + pref[0][cord];
}
if(N == 2)
{
sum = max(pref[0][1], pref[1][1]);
}
return sum;
}
long long group3(int N, int M, vector <int> X, vector <int> Y, vector <int> W)
{
long long dp[2][N], a[N];
for(int i = 0; i < N; i++)
{
dp[0][i] = 0;
dp[1][i] = 0;
a[i] = 0;
}
for(int i = 0; i < M; i++)
{
a[X[i]] = W[i];
}
for(int i = 1; i < N; i++)
{
if(i > 1)
{
dp[1][i] = max(max(dp[0][i - 2] + a[i - 1], dp[1][i - 2] + a[i - 1]), dp[1][i - 1]);
}
else
{
dp[1][i] = dp[0][i - 1] + a[i - 1];
}
dp[0][i] = max(dp[0][i - 1], dp[1][i - 1] + a[i]);
}
if(N > 1)
{
return max(max(dp[0][N - 1], dp[1][N - 1]), max(dp[0][N - 2], dp[1][N - 2]));
}
else
{
return max(dp[0][N - 1], dp[1][N - 1]);
}
}
long long group4()
{
}
long long group5()
{
}
long long group6()
{
}
long long group7()
{
}
long long full()
{
}
long long max_weights(int N, int M, vector <int> X, vector <int> Y, vector <int> W)
{
bool flag1 = true;
bool flag2 = true;
bool flag3 = true;
bool flag4 = true;
for(int i = 0; i < M; i++)
{
if(X[i] % 2 != 0)
{
flag1 = false;
}
if(X[i] > 1)
{
flag2 = false;
}
if(Y[i] != 0)
{
flag3 = false;
}
if(Y[i] > 8)
{
flag4 = false;
}
}
//cout << flag1 << " " << flag2 << " " << flag3 << " " << flag4 << endl;
if(flag1)
{
return group1(W);
}
if(flag2)
{
return group2(N, M, X, Y, W);
}
if(flag3)
{
return group3(N, M, X, Y, W);
}
if(flag4)
{
return group4();
}
return 0;
}
/**
int main()
{
ios_base::sync_with_stdio(false);
cout << max_weights(3, 3, {0, 1, 2}, {0, 0, 0}, {1, 1, 1});
}
/**/
