#include <bits/stdc++.h>
long long solve(vector<vector<int>>&arr,int i,int prev,int n,int m,vector<vector<long long>>&dp){
if(i>=n)return 0;
if(dp[i][prev]!=-1)return dp[i][prev];
long long ans = 0;
for(int col=0;col<m;col++){
if(prev!=col){
long long val = arr[i][col] + solve(arr,i+1,col,n,m,dp);
ans = max(ans , val);
}
}
return dp[i][prev] = ans;
}
int ninjaTraining(int n, vector<vector<int>> &arr)
{
// Write your code here.
int m = arr[0].size();
vector<vector<long long>>dp(n,vector<long long>(m,-1));
long long ans = -1e9;
for(int i=0;i<m;i++){
ans = max(ans , arr[0][i] + solve(arr,1,i,n,m,dp));
}
return ans;
}