#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define sz(x) (ll)x.size()
#define F first
#define S second
#define pb push_back
#define MID ((l+r)/2)
#define dbg(x) cout<<#x<<": "<<x<<endl;
#define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl;
typedef vector <ll> vi;
typedef vector <long long > vl;
typedef pair <ll,ll> ii;
typedef vector <ii> vii;
void printVct(vl &v, string s = ""){
cout<<s<<": ";
for (ll i=0; i<sz(v); i++){
cout<<v[i]<<" ";
}
cout<<endl;
}
#define printArr2D(arr, n, m, s) cout<<s<<": "<<endl; for (ll i=0; i<n; i++){ cout<<i<<": "; for (ll j =0; j<m; j++){cout<<arr[i][j]<<" ";}cout<<endl;} cout<<endl;
#define N 300
#define MAXY 9 // Y[i] + 1
ll n,m;
long long arr[N+1][MAXY+1];
long long dp[N+1][MAXY+1][MAXY+1];
long long s[N+1][MAXY+1];
long long calc(ll u, ll l, ll r){ // 0 <= x <= 9
if (u < 0){
cout<<"ERROR!! "<<u<<" "<<l<<" "<<r<<endl<<endl;
exit(1);
}
if (l > r){
return 0;
}
l--, r--;
if (l == 0){
return s[u][r];
}
else{
return s[u][r] - s[u][l-1];
}
}
void printDP(ll l = 0, ll r = MAXY){
for (ll k=l; k<=r; k++){
cout<<"k: "<<k<<endl;
for (ll i = 0; i<n; i++){
cout<<i<<": ";
for (ll j =0; j<=MAXY; j++){
cout<<dp[i][j][k];
}
cout<<endl;
}
cout<<endl;
}
cout<<endl;
}
long long solve(){
//prep line 0
for (ll j =0; j<=MAXY; j++){
for (ll k =0; k<=MAXY; k++){
dp[0][j][k] = 0;
}
}
//prep line 1
for (ll j =0; j<=MAXY; j++){
for (ll k =0; k<=MAXY; k++){
if (j == k) dp[1][j][k] = 0;
else if (j > k){
dp[1][j][k] = calc(0, k+1, j);
}
else{
dp[1][j][k] = calc(1, j+1, k);
}
}
}
// printDP();
//solve
for (ll i =2; i<n; i++){
for (ll j = 0; j<=MAXY; j++){
for (ll k =0; k<=MAXY; k++){
long long ans = 0, c;
for (ll y =0; y<=j; y++){
c = dp[i-1][k][y] + calc(i-1, max(y,k+1), j); //chek indexes
ans=max(ans, c);
}
for (ll y =j+1; y<=MAXY; y++){
c = dp[i-1][k][y];
ans = max(ans, c);
}
dp[i][j][k] = ans;
}
}
}
// printDP();
long long ans =0;
for (ll i =0; i<n; i++){
for (ll j =0; j<=MAXY; j++){
for (ll k =0; k<=MAXY; k++){
ans = max(ans, dp[i][j][k]);
}
}
}
return ans;
}
long long max_weights(int NN, int M, vi X, vi Y, vi W) {
n= NN, m =M;
for (ll i =0 ; i<m; i++){
arr[X[i]][Y[i]] = W[i];
}
for (ll i =0; i<n; i++){
s[i][0] = arr[i][0];
for (ll j = 1; j< MAXY; j++){
s[i][j] = s[i][j-1] + arr[i][j];
}
}
// printArr2D(s,n,MAXY,"s");
long long ans = solve();
return ans;
}
/*
116037261256
216624184325
=> our answer is less
*/
