#include <bits/stdc++.h>
using namespace std;
namespace {
using int64 = long long;
const int64 inf = 1e15;
}; // namespace
int64 max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
for (int &i : Y) {
i++;
}
const int ht = N;
vector grid(5, vector<int64>(ht + 1));
for (int i = 0; i < M; ++i) {
grid[X[i]][Y[i]] += W[i];
}
for (int i = 0; i < 5; ++i) {
partial_sum(grid[i].begin(), grid[i].end(), grid[i].begin());
}
auto get = [&](vector<int> hts) {
int64_t ans = 0;
int p1 = 0, p2 = 0;
for (int i = 0; i < int(hts.size()); ++i) {
int cur = hts[i];
int64 base = 0;
// delete stuff got by p1 but we fucked
base -= grid[i][min(p1, cur)];
// in column i-1, get stuff from max(p1,p2)+1 to cur
if (i - 1 >= 0 && max(p1, p2) + 1 <= cur) {
base += grid[i - 1][cur] - grid[i - 1][max(p1, p2)];
}
// in column i+1, get stuff from 0 to cur
if (i + 1 < 5) {
base += grid[i + 1][cur];
}
ans += base;
p2 = p1, p1 = cur;
}
return ans;
};
int64_t ans = 0;
// first make pillar at 0 smaller
for (int shar = 0; shar <= N; ++shar) {
int h0 = shar, h1 = N;
if (N == 2) {
ans = max(ans, get({h0, h1}));
} else {
ans = max(ans, get({h0, h1, N}));
}
}
// now make pillar at 1 smaller
for (int shar = 0; shar <= N; ++shar) {
int h0 = N, h1 = shar;
if (N == 2) {
ans = max(ans, get({h0, h1}));
} else {
ans = max(ans, get({h0, h1, N}));
}
}
return ans;
}
