stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

#define ll long long int

#include <ext/pb_ds/assoc_container.hpp> 

#include <ext/pb_ds/tree_policy.hpp> 

using namespace __gnu_pbds;   

#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 

#define ld long double

#define ff first

#define ss second

#define pb push_back

#define mp make_pair

#define all(a) a.begin(),a.end()

#define sz(a) (ll)(a.size())

const int M=1e5+5;

std::vector<int> vtr[M];

set<int> st;

ll dfs(int x)

{

	int sb = 1;

	for(auto u:vtr[x])

		sb = sb + dfs(u);

	// cout<<sb<<endl;

	st.insert(sb);

	return sb;

}

int main()

{

	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

	string s;

	cin>>s;

	s = "#"+s;

	int n=sz(s)-1;

	if(s[n]=='1' || s[1]=='0')

	{

		cout<<"-1\n";

		return 0;

	}

	for(int i=1;i<n;i++)

	{

		if(s[i]!=s[n-i])

		{

			cout<<"-1\n";

			return 0;

		}

	}

	for(int i=1;i<=n-1;i++)

	{

		if(s[i]=='0')

			continue;

		int j=i+1;

		while(j<n-1 && s[j]=='0')

			j++;

		for(int k=i;k<j;k++)

		{

			vtr[j].pb(k);

		}

	}

	dfs(n);

	for(int i=1;i<n;i++)

	{

		if(s[i]=='1')

		{

			if(st.find(i)==st.end())

			{

				cout<<"-1\n";

				return 0;

			}

		}

		else

		{

			if(st.find(i)!=st.end() || st.find(n-i)!=st.end())

			{

				cout<<"-1\n";

				return 0;

			}

		}



	}

	for(int i=1;i<=n;i++)

	{

		for(auto u:vtr[i])

			cout<<i<<" "<<u<<"\n";

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.503909178894526x):
#include <bits/stdc++.h>

using namespace std;

#define ll long long int

#include <ext/pb_ds/assoc_container.hpp> 

#include <ext/pb_ds/tree_policy.hpp> 

using namespace __gnu_pbds;   

#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 

#define ld long double

#define ff first

#define ss second

#define pb push_back

#define mp make_pair

#define all(a) a.begin(),a.end()

#define sz(a) (ll)(a.size())

int main()

{

	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

	string s;

	cin>>s;

	s = "#"+s;

	int n=sz(s)-1;

	if(s[n]=='1' || s[1]=='0')

	{

		cout<<"-1\n";

		return 0;

	}

	for(int i=1;i<n;i++)

	{

		if(s[i]!=s[n-i])

		{

			cout<<"-1\n";

			return 0;

		}

	}

	for(int i=1;i<=n-1;i++)

	{

		if(s[i]=='0')

			continue;

		int j=i+1;

		while(j<n-1 && s[j]=='0')

			j++;

		for(int k=i;k<j;k++)

		{

			cout<<j<<" "<<k<<"\n";

		}

	}

}
// Slower C++ solution:
#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

char ch[100010];

int n,x,pos,cnt=0;

int lian[100010],head[100010];

struct node{

	int to,nxt,cap;

}e[200010];

void add(int u,int v){

	e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;

}

int main(){

	scanf("%s",ch+1);

	n=strlen(ch+1);

	int i,j;

	for(i=1;i<=n;++i)  lian[i]=ch[i]-48;

	if(lian[n]!=0 || lian[1]==0){printf("-1\n");return 0;}

	for(i=1;i<=n;++i){

		if(lian[i]^lian[n-i]){printf("-1\n");return 0;}

	}

	x=(n+1)/2;pos=x+1;

	for(i=pos+1;i<=n;++i)  add(pos,i);

	for(i=x;i>=1;--i){

		add(pos,i);

		if(lian[i])  pos=i;

	}

	for(j=1;j<=n;++j){

		for(i=head[j];i;i=e[i].nxt){

			printf("%d %d\n",j,e[i].to);

		}

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.281492130624117x):
#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#define reg register

using namespace std;

typedef long long ll;

const int MN=1e5+5;

int n,x[MN],y[MN];

char ch[MN];

int main(){

	scanf("%s",ch+1);n=strlen(ch+1);

	if((ch[n]^48)||!(ch[1]^48))return 0*puts("-1");

	for(reg int i=1;i<=(n>>1);i++)if(ch[i]^ch[n-i])return 0*puts("-1");

	reg int pre=1;

	for(reg int i=2;i<=n;i++)if(ch[i]^48)for(;pre<i;pre++)printf("%d %d\n",pre,i);

	printf("%d %d\n",n-1,n);

	return 0;

}
// Slower C++ solution:
#include <cstdio>

#include <set>

#include <cstring>



using std::set;



int u[101000], v[101000], tot = 0;

char c[101000];

set<int> st;



void dfs(int x, int siz)

{

	int rt = x;

	siz--; x++;

	while(1)

	{

		set<int>::iterator it = st.lower_bound(siz); 

		if(st.size() == 0 || (it == st.begin() && (*it) != siz)) break;

		if((*it) != siz) --it;

		u[++tot] = rt; v[tot] = x;

		int new_rt = x;

		x += (*it); siz -= (*it);

		st.erase(it);

		dfs(new_rt, (*it));

	}

	while(siz) u[++tot] = rt, v[tot] = x, x++, siz--;

}

int main()

{

	scanf("%s", c + 1);

	int n = strlen(c + 1);

	for(int i = 1; i <= (n >> 1); i++)

	{

		if(c[i] != c[n - i]) return 0 * puts("-1");

	}

	if(c[1] != '1' || c[n] == '1') return 0 * puts("-1");

	for(int i = 2; i <= (n >> 1); i++) if(c[i] == '1') st.insert(i);

	dfs(1, n);

	if(st.size() != 0) return 0 * puts("-1");

	for(int i = 1; i < n; i++) printf("%d %d\n", u[i], v[i]);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 4.912679283004449x):
#include<cstdio>

#include<cstring>

#include<algorithm>

#define MN 100005

using namespace std;

inline int in(){

    int x=0;bool f=0;char c;

    for (;(c=getchar())<'0'||c>'9';f=c=='-');

    for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0');

    return f?-x:x;

}

char s[MN];

int x[MN],y[MN],b[MN];

int n,tot,cnt;

bool a[MN];

int main()

{

	scanf("%s",s);n=strlen(s);

	for (int i=1;i<=n;++i) a[i]=s[i-1]-'0'; 

	for (int i=1;i<=n-i;++i)

	if (a[i]^a[n-i]) {printf("-1");return 0;}

	if ((!a[1])||a[n]) {printf("-1");return 0;}

	for (int i=1;i<=n;++i) if (a[i]) b[++tot]=i;

	for (int i=2;i<=tot;++i){

		x[++cnt]=b[i-1];y[cnt]=b[i];

		for (int j=b[i-1]+1;j<b[i];++j)

		x[++cnt]=j,y[cnt]=b[i];

	}if (b[tot]!=n-1) {printf("-1");return 0;}

	for (int i=1;i<=cnt;++i)

	printf("%d %d\n",x[i],y[i]);

	printf("%d %d\n",n-1,n);return 0;

}
// Slower C++ solution:
#include <cstdio>

#include <set>

#include <cstring>



using std::set;



int u[101000], v[101000], tot = 0;

char c[101000];

set<int> st;



void dfs(int x, int siz)

{

	int rt = x;

	siz--; x++;

	while(1)

	{

		set<int>::iterator it = st.lower_bound(siz); 

		if(st.size() == 0 || (it == st.begin() && (*it) != siz)) break;

		if((*it) != siz) --it;

		u[++tot] = rt; v[tot] = x;

		int new_rt = x;

		x += (*it); siz -= (*it);

		st.erase(it);

		dfs(new_rt, (*it));

	}

	while(siz) u[++tot] = rt, v[tot] = x, x++, siz--;

}

int main()

{

	scanf("%s", c + 1);

	int n = strlen(c + 1);

	for(int i = 1; i <= (n >> 1); i++)

	{

		if(c[i] != c[n - i]) return 0 * puts("-1");

	}

	if(c[1] != '1' || c[n] == '1') return 0 * puts("-1");

	for(int i = 2; i <= (n >> 1); i++) if(c[i] == '1') st.insert(i);

	dfs(1, n);

	if(st.size() != 0) return 0 * puts("-1");

	for(int i = 1; i < n; i++) printf("%d %d\n", u[i], v[i]);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 4.935392567042307x):
#include <cstdio>

#include <cstring>

#define fail return puts("-1"), 0



const int N = 1e5 + 5;



char s[N];



int main() {

	scanf("%s", s + 1);

	int n = strlen(s + 1);

	if (s[1] == '0' || s[n] == '1') fail;

	for (int i = 1; i < n; i++) {

		if (s[i] != s[n - i]) fail;

	}

	for (int i = 2, r = 1; i <= n; i++) {

		printf("%d %d\n", r, i);

		if (s[i - 1] == '1') r = i;

	}

	return 0;

}
// Slower C++ solution:
// in the name of Allah ;

#include<bits/stdc++.h>

using namespace std ;

const int maxn = 1e5 + 10 ;

string s ;

vector < pair < int , int > > ans ;

int n ;

bool valid () 

{

	for ( int i = 0 ; i < n-1 ; i++ ) 

	{

		if ( s[i] != s[n-2-i] ) 

			return false ;

	}

	if ( s[0] != '1' || s[n-1]!= '0' ) 

		return false ; 

	return true ;

}

int main () 

{

	cin>> s ;

	n = s.size() ;

	if ( !valid () ) 

	{

		cout << -1 << endl;

		return 0 ;

	}

	int p = 0 ; 

	for ( int i = 0 ; i < n-1 ; i++ ) 

		if ( s[i] == '1' ) 

			ans.push_back ( { p , i+1 } ) , p = i+1  ;

		else

			 ans.push_back ( { p , i+1} )   ;

	for ( auto tmp : ans ) 

		cout << tmp.first+1 << " " << tmp.second+1 << endl;

}

// Faster C++ solution for the same problem (measured speedup: 5.350279518333476x):
#include <cstdio>

#include <cstring>

#define fail return puts("-1"), 0



const int N = 1e5 + 5;



char s[N];



int main() {

	scanf("%s", s + 1);

	int n = strlen(s + 1);

	if (s[1] == '0' || s[n] == '1') fail;

	for (int i = 1; i < n; i++) {

		if (s[i] != s[n - i]) fail;

	}

	for (int i = 2, r = 1; i <= n; i++) {

		printf("%d %d\n", r, i);

		if (s[i - 1] == '1') r = i;

	}

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



const int N = 1e5 + 10;



char s[N];



int main(){

	int n, flag, now;

	scanf("%s", s + 1);

	n = strlen(s + 1);

	if (s[n] == '1'){

		printf("-1\n");

		return 0;

	} 

	if (s[1] == '0' || s[n - 1] == '0'){

		printf("-1\n");

		return 0;

	}

	flag = 1;

	for (int i = 1; i <= (n - 1) / 2; i++){

		if (s[i] != s[n - i]){

			flag = 0;

			break;

		}

	}

	if (!flag){

		printf("-1\n");

		return 0;

	}

	now = 1;

	for (int i = 1; i <= n / 2; i++){

		printf("%d %d\n", now, i + 1);

		if (s[i] == '1') now = i + 1;

	}

	for (int i = n / 2 + 2; i <= n; i++) printf("%d %d\n", now, i);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.277730495785429x):
#include <cstdio>

#include <cstring>

#define fail return puts("-1"), 0



const int N = 1e5 + 5;



char s[N];



int main() {

	scanf("%s", s + 1);

	int n = strlen(s + 1);

	if (s[1] == '0' || s[n] == '1') fail;

	for (int i = 1; i < n; i++) {

		if (s[i] != s[n - i]) fail;

	}

	for (int i = 2, r = 1; i <= n; i++) {

		printf("%d %d\n", r, i);

		if (s[i - 1] == '1') r = i;

	}

	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cstring>

using namespace std;



int main(){

  int n,mp[302][302],x[302][302]={},y[302][302]={};

  cin>>n;

  for(int i=0;i<n;i++)

    for(int j=0;j<n;j++)cin>>y[i][j],mp[i][j]=x[i][j]=y[i][j];

  

  int ans=max(y[0][n-1],y[n-1][0]);

  for(int i=0;i<n;i++)

    for(int j=n-2;j>=0;j--) {

      x[i][j]+=x[i][j+1];

      y[j][i]+=y[j+1][i];

      if(ans<x[i][j])ans=x[i][j];

      if(ans<y[j][i])ans=y[j][i];

    }





  int sum[302][302],K[2][302][302]={};





  for(int i=0;i<=n;i++)

    for(int j=0;j<=n;j++) sum[i][j]=-100000000;



  int t=0;

  while(1){

    t++;

    for(int i=0;i<n;i++) //yoko

      for(int j=i+1;j<n;j++) {//yoko

	int a=K[t%2][i][j];

	K[(t+1)%2][i][j]=a;

	sum[i][j]=-100000000;

	for(int k=a+1;k<n;k++) { //tate

	  int X=(x[a][i]-x[a][j+1])+(x[k][i]-x[k][j+1]);

	  int Y=(y[a+1][i]-y[k][i])+(y[a+1][j]-y[k][j]);

	  if(sum[i][j]<=X+Y)sum[i][j]=X+Y,K[(t+1)%2][i][j]=k;

	  ans=max(ans,sum[i][j]);

	}

      }



    int f=1;

    for(int i=0;i<n;i++) //yoko

      for(int j=i+1;j<n;j++) //yoko

	for(int k=K[t%2][i][j]+1;k<K[(t+1)%2][i][j];k++){

	  f=0;

	  int X=(x[k][i+1]-x[k][j])-(x[k-1][i]-x[k-1][j+1]);

	  sum[i][j]+=X;

	  ans=max(ans,sum[i][j]);

	}

    if(f)break;

  }

  cout <<ans<<endl;

	  

  return 0; 

}

// Faster C++ solution for the same problem (measured speedup: 1.1785432899750525x):
#include <iostream>

#define INF 10000000

using namespace std;



int main(){

  int n,x[302][302]={},y[302][302]={};

  cin>>n;

  for(int i=0;i<n;i++)

    for(int j=0;j<n;j++)cin>>y[i][j],x[i][j]=y[i][j];



  /*  for(int i=0;i<300;i++)

    for(int j=0;j<300;j++) y[i][j]=x[i][j]=-1;

    n=300;*/

  

  for(int i=0;i<n;i++)

    for(int j=n-2;j>=0;j--) {

      x[i][j]+=x[i][j+1];

      y[j][i]+=y[j+1][i];

    }



  int ans=max(y[0][n-1],y[n-1][0]),sum,K[302][302]={},t=0,f=1;

  while(f){

    t++,f=0;

    for(int i=0;i<n;i++) //yoko

      for(int j=i+1;j<n;j++) {//yoko

	int a=K[i][j],nk=a;

	sum=-INF;

	for(int k=a+1;k<n;k++) { //tate

	  int X=(x[a][i]-x[a][j+1])+(x[k][i]-x[k][j+1]);

	  int Y=(y[a+1][i]-y[k][i])+(y[a+1][j]-y[k][j]);

	  if(sum<=X+Y)sum=X+Y,nk=k;

	}

	ans=max(ans,sum);

	

	if(nk!=n-1)f=1;

	for(int k=a+1;k<nk;k++){//tate

	  sum+=(x[k][i+1]-x[k][j])-(x[k-1][i]-x[k-1][j+1]);

	  ans=max(ans,sum);

	  }

	K[i][j]=nk;

      }

  }

  cout <<ans<<endl;

	  

  return 0; 

}
// Slower C++ solution:
#include <iostream>

#include <cstring>

using namespace std;



int main(){

  int n,x[302][302]={},y[302][302]={};

  cin>>n;

  for(int i=0;i<n;i++)

    for(int j=0;j<n;j++)cin>>y[i][j],x[i][j]=y[i][j];

  

  int ans=max(y[0][n-1],y[n-1][0]);

  for(int i=0;i<n;i++)

    for(int j=n-2;j>=0;j--) {

      x[i][j]+=x[i][j+1];

      y[j][i]+=y[j+1][i];

      ans=max(ans,max(y[j][i],x[i][j]));

    }



  int sum[302][302],K[2][302][302]={};

  for(int i=0;i<=n;i++)

    for(int j=0;j<=n;j++) sum[i][j]=-100000000;





  int t=0,f=1;

  while(f){

    t++,f=0;



    for(int i=0;i<n;i++) //yoko

      for(int j=i+1;j<n;j++) {//yoko

	int a=K[t%2][i][j];

	K[(t+1)%2][i][j]=a;

	sum[i][j]=-100000000;

	for(int k=a+1;k<n;k++) { //tate

	  int X=(x[a][i]-x[a][j+1])+(x[k][i]-x[k][j+1]);

	  int Y=(y[a+1][i]-y[k][i])+(y[a+1][j]-y[k][j]);

	  if(sum[i][j]<=X+Y)sum[i][j]=X+Y,K[(t+1)%2][i][j]=k;

	  ans=max(ans,sum[i][j]);

	}

	if(K[t%2][i][j]!=n-1)f=1;

	for(int k=K[t%2][i][j]+1;k<K[(t+1)%2][i][j];k++){//tate

	  sum[i][j]+=(x[k][i+1]-x[k][j])-(x[k-1][i]-x[k-1][j+1]);

	  ans=max(ans,sum[i][j]);

	}

      }

  }

  cout <<ans<<endl;

	  

  return 0; 

}

// Faster C++ solution for the same problem (measured speedup: 1.1787472182455916x):
#include <iostream>

#define INF 10000000

using namespace std;



int main(){

  int n,x[302][302]={},y[302][302]={};

  cin>>n;

  for(int i=0;i<n;i++)

    for(int j=0;j<n;j++)cin>>y[i][j],x[i][j]=y[i][j];



  /*  for(int i=0;i<300;i++)

    for(int j=0;j<300;j++) y[i][j]=x[i][j]=-1;

    n=300;*/

  

  for(int i=0;i<n;i++)

    for(int j=n-2;j>=0;j--) {

      x[i][j]+=x[i][j+1];

      y[j][i]+=y[j+1][i];

    }



  int ans=max(y[0][n-1],y[n-1][0]),sum,K[302][302]={},t=0,f=1;

  while(f){

    t++,f=0;

    for(int i=0;i<n;i++) //yoko

      for(int j=i+1;j<n;j++) {//yoko

	int a=K[i][j],nk=a;

	sum=-INF;

	for(int k=a+1;k<n;k++) { //tate

	  int X=(x[a][i]-x[a][j+1])+(x[k][i]-x[k][j+1]);

	  int Y=(y[a+1][i]-y[k][i])+(y[a+1][j]-y[k][j]);

	  if(sum<=X+Y)sum=X+Y,nk=k;

	}

	ans=max(ans,sum);

	

	if(nk!=n-1)f=1;

	for(int k=a+1;k<nk;k++){//tate

	  sum+=(x[k][i+1]-x[k][j])-(x[k-1][i]-x[k-1][j+1]);

	  ans=max(ans,sum);

	  }

	K[i][j]=nk;

      }

  }

  cout <<ans<<endl;

	  

  return 0; 

}
// Slower C++ solution:
#include <iostream>

using namespace std;



int main(){

  int n,x[302][302]={},y[302][302]={};

  cin>>n;

  for(int i=0;i<n;i++)

    for(int j=0;j<n;j++)cin>>y[i][j],x[i][j]=y[i][j];

  

  int ans=max(y[0][n-1],y[n-1][0]);

  for(int i=0;i<n;i++)

    for(int j=n-2;j>=0;j--) {

      x[i][j]+=x[i][j+1];

      y[j][i]+=y[j+1][i];

      ans=max(ans,max(y[j][i],x[i][j]));

    }



  

  int sum[302][302],K[2][302][302]={},t=0,f=1;

  while(f){

    t++,f=0;

    for(int i=0;i<n;i++) //yoko

      for(int j=i+1;j<n;j++) {//yoko

	int a=K[t%2][i][j],&b=K[(t+1)%2][i][j];



	b=a;

	sum[i][j]=-10000000;



	for(int k=a+1;k<n;k++) { //tate

	  int X=(x[a][i]-x[a][j+1])+(x[k][i]-x[k][j+1]);

	  int Y=(y[a+1][i]-y[k][i])+(y[a+1][j]-y[k][j]);

	  if(sum[i][j]<=X+Y)sum[i][j]=X+Y,b=k;

	}

	

	if(b!=n-1)f=1;

	ans=max(ans,sum[i][j]);

	for(int k=a+1;k<b;k++){//tate

	  sum[i][j]+=(x[k][i+1]-x[k][j])-(x[k-1][i]-x[k-1][j+1]);

	  ans=max(ans,sum[i][j]);

	}

      }

  }

  cout <<ans<<endl;

	  

  return 0; 

}

// Faster C++ solution for the same problem (measured speedup: 1.1749540996507497x):
#include <iostream>

#define INF 10000000

using namespace std;



int main(){

  int n,x[302][302]={},y[302][302]={};

  cin>>n;

  for(int i=0;i<n;i++)

    for(int j=0;j<n;j++)cin>>y[i][j],x[i][j]=y[i][j];



  /*  for(int i=0;i<300;i++)

    for(int j=0;j<300;j++) y[i][j]=x[i][j]=-1;

    n=300;*/

  

  for(int i=0;i<n;i++)

    for(int j=n-2;j>=0;j--) {

      x[i][j]+=x[i][j+1];

      y[j][i]+=y[j+1][i];

    }



  int ans=max(y[0][n-1],y[n-1][0]),sum,K[302][302]={},t=0,f=1;

  while(f){

    t++,f=0;

    for(int i=0;i<n;i++) //yoko

      for(int j=i+1;j<n;j++) {//yoko

	int a=K[i][j],nk=a;

	sum=-INF;

	for(int k=a+1;k<n;k++) { //tate

	  int X=(x[a][i]-x[a][j+1])+(x[k][i]-x[k][j+1]);

	  int Y=(y[a+1][i]-y[k][i])+(y[a+1][j]-y[k][j]);

	  if(sum<=X+Y)sum=X+Y,nk=k;

	}

	ans=max(ans,sum);

	

	if(nk!=n-1)f=1;

	for(int k=a+1;k<nk;k++){//tate

	  sum+=(x[k][i+1]-x[k][j])-(x[k-1][i]-x[k-1][j+1]);

	  ans=max(ans,sum);

	  }

	K[i][j]=nk;

      }

  }

  cout <<ans<<endl;

	  

  return 0; 

}
// Slower C++ solution:
#include <iostream>

using namespace std;



int main(){

  int n,x[302][302]={},y[302][302]={};

  cin>>n;

  for(int i=0;i<n;i++)

    for(int j=0;j<n;j++)cin>>y[i][j],x[i][j]=y[i][j];

  

  int ans=max(y[0][n-1],y[n-1][0]);

  for(int i=0;i<n;i++)

    for(int j=n-2;j>=0;j--) {

      x[i][j]+=x[i][j+1];

      y[j][i]+=y[j+1][i];

    }



  

  int sum[302][302],K[2][302][302]={},t=0,f=1;

  while(f){

    t++,f=0;

    for(int i=0;i<n;i++) //yoko

      for(int j=i+1;j<n;j++) {//yoko

	int a=K[t%2][i][j],&b=K[(t+1)%2][i][j];

	b=a+1;

	sum[i][j]=-10000000;



	for(int k=a+1;k<n;k++) { //tate

	  int X=(x[a][i]-x[a][j+1])+(x[k][i]-x[k][j+1]);

	  int Y=(y[a+1][i]-y[k][i])+(y[a+1][j]-y[k][j]);

	  if(sum[i][j]<=X+Y)sum[i][j]=X+Y,b=k;

	}

	

	if(b<=n-1)f=1;

	ans=max(ans,sum[i][j]);

	for(int k=a+1;k<b;k++){//tate

	  sum[i][j]+=(x[k][i+1]-x[k][j])-(x[k-1][i]-x[k-1][j+1]);

	  ans=max(ans,sum[i][j]);

	}

      }

  }

  cout <<ans<<endl;

	  

  return 0; 

}

// Faster C++ solution for the same problem (measured speedup: 1.1747417293302012x):
#include <iostream>

#define INF 10000000

using namespace std;



int main(){

  int n,x[302][302]={},y[302][302]={};

  cin>>n;

  for(int i=0;i<n;i++)

    for(int j=0;j<n;j++)cin>>y[i][j],x[i][j]=y[i][j];



  /*  for(int i=0;i<300;i++)

    for(int j=0;j<300;j++) y[i][j]=x[i][j]=-1;

    n=300;*/

  

  for(int i=0;i<n;i++)

    for(int j=n-2;j>=0;j--) {

      x[i][j]+=x[i][j+1];

      y[j][i]+=y[j+1][i];

    }



  int ans=max(y[0][n-1],y[n-1][0]),sum,K[302][302]={},t=0,f=1;

  while(f){

    t++,f=0;

    for(int i=0;i<n;i++) //yoko

      for(int j=i+1;j<n;j++) {//yoko

	int a=K[i][j],nk=a;

	sum=-INF;

	for(int k=a+1;k<n;k++) { //tate

	  int X=(x[a][i]-x[a][j+1])+(x[k][i]-x[k][j+1]);

	  int Y=(y[a+1][i]-y[k][i])+(y[a+1][j]-y[k][j]);

	  if(sum<=X+Y)sum=X+Y,nk=k;

	}

	ans=max(ans,sum);

	

	if(nk!=n-1)f=1;

	for(int k=a+1;k<nk;k++){//tate

	  sum+=(x[k][i+1]-x[k][j])-(x[k-1][i]-x[k-1][j+1]);

	  ans=max(ans,sum);

	  }

	K[i][j]=nk;

      }

  }

  cout <<ans<<endl;

	  

  return 0; 

}
// Slower C++ solution:
#include <iostream>

#define INF 10000000

using namespace std;



int main(){

  int n,x[302][302]={},y[302][302]={};

  cin>>n;

  for(int i=0;i<n;i++)

    for(int j=0;j<n;j++)cin>>y[i][j],x[i][j]=y[i][j];

  

  for(int i=0;i<n;i++)

    for(int j=n-2;j>=0;j--) {

      x[i][j]+=x[i][j+1];

      y[j][i]+=y[j+1][i];

    }



  int ans=max(y[0][n-1],y[n-1][0]),sum[302][302],K[2][302][302]={},t=0,f=1;

  while(f){

    t++,f=0;

    for(int i=0;i<n;i++) //yoko

      for(int j=i+1;j<n;j++) {//yoko

	int a=K[t%2][i][j],&b=K[(t+1)%2][i][j];

	b=a;

	sum[i][j]=-INF;



	for(int k=a+1;k<n;k++) { //tate

	  int X=(x[a][i]-x[a][j+1])+(x[k][i]-x[k][j+1]);

	  int Y=(y[a+1][i]-y[k][i])+(y[a+1][j]-y[k][j]);

	  if(sum[i][j]<=X+Y)sum[i][j]=X+Y,b=k;

	}

	ans=max(ans,sum[i][j]);



	if(b!=n-1)f=1;

	for(int k=a+1;k<b;k++){//tate

	  sum[i][j]+=(x[k][i+1]-x[k][j])-(x[k-1][i]-x[k-1][j+1]);

	  ans=max(ans,sum[i][j]);

	}

      }

  }

  cout <<ans<<endl;

	  

  return 0; 

}

// Faster C++ solution for the same problem (measured speedup: 1.1747718041333597x):
#include <iostream>

#define INF 10000000

using namespace std;



int main(){

  int n,x[302][302]={},y[302][302]={};

  cin>>n;

  for(int i=0;i<n;i++)

    for(int j=0;j<n;j++)cin>>y[i][j],x[i][j]=y[i][j];



  /*  for(int i=0;i<300;i++)

    for(int j=0;j<300;j++) y[i][j]=x[i][j]=-1;

    n=300;*/

  

  for(int i=0;i<n;i++)

    for(int j=n-2;j>=0;j--) {

      x[i][j]+=x[i][j+1];

      y[j][i]+=y[j+1][i];

    }



  int ans=max(y[0][n-1],y[n-1][0]),sum,K[302][302]={},t=0,f=1;

  while(f){

    t++,f=0;

    for(int i=0;i<n;i++) //yoko

      for(int j=i+1;j<n;j++) {//yoko

	int a=K[i][j],nk=a;

	sum=-INF;

	for(int k=a+1;k<n;k++) { //tate

	  int X=(x[a][i]-x[a][j+1])+(x[k][i]-x[k][j+1]);

	  int Y=(y[a+1][i]-y[k][i])+(y[a+1][j]-y[k][j]);

	  if(sum<=X+Y)sum=X+Y,nk=k;

	}

	ans=max(ans,sum);

	

	if(nk!=n-1)f=1;

	for(int k=a+1;k<nk;k++){//tate

	  sum+=(x[k][i+1]-x[k][j])-(x[k-1][i]-x[k-1][j+1]);

	  ans=max(ans,sum);

	  }

	K[i][j]=nk;

      }

  }

  cout <<ans<<endl;

	  

  return 0; 

}
// Slower C++ solution:
#include <iostream>

#include <cstring>

using namespace std;



int main(){

  int n,mp[302][302],x[302][302]={},y[302][302]={};

  cin>>n;

  for(int i=0;i<n;i++)

    for(int j=0;j<n;j++)cin>>y[i][j],mp[i][j]=x[i][j]=y[i][j];

  

  int ans=max(y[0][n-1],y[n-1][0]);

  for(int i=0;i<n;i++)

    for(int j=n-2;j>=0;j--) {

      x[i][j]+=x[i][j+1];

      y[j][i]+=y[j+1][i];

      if(ans<x[i][j])ans=x[i][j];

      if(ans<y[j][i])ans=y[j][i];

    }





  int sum[302][302],K[2][302][302]={};





  for(int i=0;i<=n;i++)

    for(int j=0;j<=n;j++) sum[i][j]=-100000000;



  int t=0;

  while(1){

    t++;

    for(int i=0;i<n;i++) //yoko

      for(int j=i+1;j<n;j++) {//yoko

	int a=K[t%2][i][j];

	K[(t+1)%2][i][j]=a;

	sum[i][j]=-100000000;

	for(int k=a+1;k<n;k++) { //tate

	  int X=(x[a][i]-x[a][j+1])+(x[k][i]-x[k][j+1]);

	  int Y=(y[a+1][i]-y[k][i])+(y[a+1][j]-y[k][j]);

	  if(sum[i][j]<=X+Y)sum[i][j]=X+Y,K[(t+1)%2][i][j]=k;

	  ans=max(ans,sum[i][j]);

	}

      }



    int f=1;

    for(int i=0;i<n;i++) //yoko

      for(int j=i+1;j<n;j++) //yoko

	for(int k=K[t%2][i][j]+1;k<K[(t+1)%2][i][j];k++){

	  f=0;

	  int X=(x[k][i+1]-x[k][j])-(x[k-1][i]-x[k-1][j+1]);

	  sum[i][j]+=X;

	  ans=max(ans,sum[i][j]);

	}

    if(f)break;

  }

  cout <<ans<<endl;

	  

  return 0; 

}

// Faster C++ solution for the same problem (measured speedup: 1.1782924339329297x):
#include <iostream>

#define INF 10000000

using namespace std;



int main(){

  int n,x[302][302]={},y[302][302]={};

  cin>>n;

  for(int i=0;i<n;i++)

    for(int j=0;j<n;j++)cin>>y[i][j],x[i][j]=y[i][j];



  for(int i=0;i<n;i++)

    for(int j=n-2;j>=0;j--) {

      x[i][j]+=x[i][j+1];

      y[j][i]+=y[j+1][i];

    }

  

  int ans=y[0][n-1],sum,K[302][302]={},t=0,f=1;

  while(f){

    t++,f=0;

    for(int i=0;i<n;i++) //yoko

      for(int j=i+1;j<n;j++) {//yoko

	int a=K[i][j],nk=a;

	sum=-INF;

	for(int k=a+1;k<n;k++) { //tate

	  int X=(x[a][i]-x[a][j+1])+(x[k][i]-x[k][j+1]);

	  int Y=(y[a+1][i]-y[k][i])+(y[a+1][j]-y[k][j]);

	  if(sum<=X+Y)sum=X+Y,nk=k;

	}

	ans=max(ans,sum);

	

	if(nk!=n-1)f=1;

	for(int k=a+1;k<nk;k++){//tate

	  sum+=(x[k][i+1]-x[k][j])-(x[k-1][i]-x[k-1][j+1]);

	  ans=max(ans,sum);

	  }

	K[i][j]=nk;

      }

  }

  cout <<ans<<endl;

	  

  return 0; 

}