#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <array>
#include <algorithm>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <random>
#include <cstdlib>
#define debug(x) std::cout << #x << " " << (x) << '\n';
#define pb push_back
#define mp std::make_pair
#define remax(a, b) a = std::max((a), (b));
#define remin(a, b) a = std::min((a), (b));
#define maxWeights max_weights
int64_t solveSmallN(int32_t n, int32_t m, std::vector<int32_t> x, std::vector<int32_t> y,
std::vector<int32_t> w) {
const int32_t MAX_N = 300;
std::array<std::array<int64_t, MAX_N>, MAX_N> wPrefSums {};
std::array<std::array<std::array<int64_t, 3>, MAX_N + 1>, MAX_N + 1> dp {};
auto getWRangeSum = [&wPrefSums](int32_t startRow, int32_t endRow, int32_t column) -> int64_t {
if(endRow <= startRow) {
return 0;
}
return wPrefSums[endRow - 1][column] - (startRow == 0 ? 0 : wPrefSums[startRow - 1][column]);
};
for(int32_t i = 0; i < m; i++) {
wPrefSums[y[i]][x[i]] = (int64_t) w[i];
}
for(int32_t j = 0; j < n; j++) {
for(int32_t i = 1; i < n; i++) {
wPrefSums[i][j] += wPrefSums[i - 1][j];
}
}
for(int32_t j = 1; j < n; j++) {
for(int32_t lastK = 0; lastK <= n; lastK++) {
for(int32_t k = 0; k <= n; k++) {
if(k == 0) {
remax(dp[j + 1][lastK][2], dp[j][lastK][0] + getWRangeSum(0, lastK, j));
remax(dp[j + 1][lastK][2], dp[j][lastK][1] + getWRangeSum(0, lastK, j));
}
if(lastK <= k) {
remax(dp[j + 1][k][0], dp[j][lastK][0] + getWRangeSum(lastK, k, j - 1));
remax(dp[j + 1][k][0], dp[j][lastK][2] + getWRangeSum(lastK, k, j - 1));
}
if(lastK >= k) {
remax(dp[j + 1][k][1], dp[j][lastK][1] + getWRangeSum(k, lastK, j));
remax(dp[j + 1][k][1], dp[j][lastK][0] + getWRangeSum(k, lastK, j));
remax(dp[j + 1][k][0], dp[j][lastK][2]);
}
}
}
}
int64_t ans = 0;
for(int32_t k = 0; k <= n; k++) {
remax(ans, dp[n][k][0]);
remax(ans, dp[n][k][1]);
remax(ans, dp[n][k][2]);
}
return ans;
}
int64_t solveEvenXs(int32_t n, int32_t m, std::vector<int32_t> x, std::vector<int32_t> y,
std::vector<int32_t> w) {
int64_t ans = 0;
for(int32_t i = 0; i < m; i++) {
ans += (int64_t) w[i];
}
return ans;
}
int64_t solveAllXs0Or1(int32_t n, int32_t m, std::vector<int32_t> x, std::vector<int32_t> y,
std::vector<int32_t> w) {
const int32_t MAX_N = 1e5;
std::array<std::array<int64_t, 2>, MAX_N> wPrefSums {};
auto getWRangeSum = [&wPrefSums](int32_t startRow, int32_t endRow, int32_t column) -> int64_t {
if(endRow <= startRow) {
return 0;
}
return wPrefSums[endRow - 1][column] - (startRow == 0 ? 0 : wPrefSums[startRow - 1][column]);
};
for(int32_t i = 0; i < m; i++) {
wPrefSums[y[i]][x[i]] = (int64_t) w[i];
}
for(int32_t j = 0; j < 2; j++) {
for(int32_t i = 1; i < n; i++) {
wPrefSums[i][j] += wPrefSums[i - 1][j];
}
}
int64_t ans = 0;
remax(ans, getWRangeSum(0, n, 1));
remax(ans, getWRangeSum(0, n, 0));
if(n > 2) {
for(int32_t i = 0; i <= n; i++) {
remax(ans, getWRangeSum(0, i, 0) + getWRangeSum(i, n, 1));
}
}
return ans;
}
int64_t solveAllYs0(int32_t n, int32_t m, std::vector<int32_t> x, std::vector<int32_t> w) {
const int32_t MAX_N = 1e5;
std::array<int32_t, MAX_N> wByColumn {};
for(int32_t i = 0; i < m; i++) {
wByColumn[x[i]] = w[i];
}
if(n == 2) {
return std::max(wByColumn[0], wByColumn[1]);
}
std::array<std::array<std::array<int64_t, 2>, 2>, MAX_N> dp {};
dp[2][0][0] = 0;
dp[2][0][1] = wByColumn[0] + wByColumn[2];
dp[2][1][0] = wByColumn[1];
dp[2][1][1] = wByColumn[2];
for(int32_t j = 3; j < n; j++) {
dp[j][0][0] = std::max(dp[j - 1][0][0], dp[j - 1][1][0]);
dp[j][0][1] = std::max(dp[j - 1][0][0], dp[j - 1][1][0]) + wByColumn[j];
dp[j][1][0] = std::max(dp[j - 1][0][1], dp[j - 1][1][1]);
dp[j][1][1] = std::max(dp[j - 1][0][1], dp[j - 1][1][1]) + wByColumn[j];
}
int64_t ans = 0;
for(int32_t i = 0; i < 2; i++) {
for(int32_t j = 0; j < 2; j++) {
remax(ans, dp[n - 1][i][j]);
}
}
return ans;
}
int64_t maxWeights(int32_t n, int32_t m, std::vector<int32_t> x, std::vector<int32_t> y,
std::vector<int32_t> w) {
if(n <= 300) {
return solveSmallN(n, m, x, y, w);
}
else if(std::all_of(x.begin(), x.end(), [](int32_t v) { return !(v & 1); })) {
return solveEvenXs(n, m, x, y, w);
}
else if(std::all_of(x.begin(), x.end(), [](int32_t v) { return (v < 2); })) {
return solveAllXs0Or1(n, m, x, y, w);
}
else {
return solveAllYs0(n, m, x, w);
}
return 0;
}
