#include "fish.h"
#include<bits/stdc++.h>
#define pb push_back
#include <vector>
using namespace std;
const int maxn = 305;
int n, m;
vector < pair < int, int > > g[200000];
long long dp[maxn][10][10];
long long pref[maxn][maxn], a[maxn][maxn];
long long get(int col, int l, int r)
{
if(r < l)return 0;
if(col > n)return 0;
long long val = pref[col][r];
if(l)val -= pref[col][l-1];
return val;
}
long long p[4][200000];
long long get_p(long long col, long long l, long long r)
{
if(r < l)return 0;
if(col > n)return 0;
long long val = p[col][r];
if(l)val -= p[col][l-1];
return val;
}
long long val[200000], d[200000][2][2];
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
n = N;
m = M;
long long sum = 0, group1 = 1, group2 = 1, group3 = 1;
for (int i = 0; i < m; ++ i)
{
if(X[i] % 2 == 1)group1 = 0;
if(X[i] > 1)group2 = 0;
if(Y[i] > 0)group3 = 0;
X[i] ++;
Y[i] ++;
g[X[i]].pb(make_pair(Y[i], W[i]));
sum += W[i];
if(n <= 300)a[X[i]][Y[i]] = W[i];
if(X[i] <= 2)p[X[i]][Y[i]] += W[i];
if(Y[i] == 1)val[X[i]] += W[i];
}
if(group1)return sum;
if(group2)
{
long long sum1 = 0, sum2 = 0;
for (auto &[y, w]: g[1])
sum1 += w;
for (auto &[y, w]: g[2])
sum2 += w;
long long ans = max(sum1, sum2);
if(n > 2)
{
for (int i = 1; i <= 2; ++ i)
{
for (int j = 1; j <= n; ++ j)
p[i][j] += p[i][j-1];
}
for (int i = 0; i <= n; ++ i)
{
long long curr = get_p(1, 1, i) + get_p(2, i+1, n);
ans = max(ans, curr);
}
}
return ans;
}
if(group3)
{
d[1][0][0] = 0;
d[1][0][1] = 0;
long long ans = 0;
if(n > 1)ans = val[2];
for (int i = 2; i <= n; ++ i)
{
/// 0
d[i][0][0] = max(d[i-1][0][0], d[i-1][1][0]);
d[i][1][0] = max(d[i-1][0][1], d[i-1][1][1]) + val[i];
/// 1
d[i][0][1] = max(d[i-1][0][0] + val[i-1], d[i-1][1][0]);
d[i][1][1] = max(d[i-1][0][1], d[i-1][1][1]);
ans = max(ans, max(d[i][0][1], d[i][1][1]) + val[i+1]);
}
return ans;
}
for (int i = 0; i <= n; ++ i)
{
pref[i][0] = a[i][0];
for (int j = 1; j <= n; ++ j)
pref[i][j] = pref[i][j-1] + a[i][j];
}
long long ans = 0;
for (int last = 0; last <= 9; ++ last)
{
for (int pre = 0; pre <= 9; ++ pre)
{
dp[2][pre][last] = get(1, pre+1, last);
ans = max(ans, dp[2][pre][last] + get(3, 1, last));
}
}
for (int i = 2; i <= n; ++ i)
{
for (int j = 0; j <= 8; ++ j)
{
for (int last = 0; last <= 9; ++ last)
{
for (int pre = 0; pre <= 9; ++ pre)
{
long long curr = dp[i-1][pre][last] + get(i, j+1, last) + get(i-1, max(pre, last) + 1, j);
dp[i][last][j] = max(dp[i][last][j], curr);
ans = max(ans, dp[i][last][j] + get(i+1, 1, j));
}
}
}
}
return ans;
}
