stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;



const int H=60*60;

const int M=60;

const int S =1;



int train[24*H+1];

int unit[3]={H,M,S};



int getTime(string s){

  string tmp;

  int res=0;

  for(int i=0;i<3;i++){

    tmp=s.substr(3*i,2);

    int val=atoi(tmp.c_str());

    res+=unit[i]*val;

  }

  return res;

}



int main(){

  int n;

  while(cin>>n,n){

    memset(train,0,sizeof(train));

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

      string start,arrival;

      int st=0,at=0;

      cin>>start>> arrival;

      st=getTime(start);

      at=getTime(arrival);

      for(int i=st;i<at;i++)train[i]++;

    }

    int ans=0;

    for(int i=0;i<=24*H;i++){

      ans=max(ans,train[i]);

      //cout << train[i] << " ";

    }

    cout << ans << endl;

  }

  return 0;

}

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

#include<vector>

#include<cstring>

#include<algorithm>

using namespace std;



typedef pair<int,int> pii;



vector<pii>train;

const int H=60*60;

const int M=60;

const int S=1;

int unit[3]={H,M,S};



int getTime(string s){

  string tmp;

  int res=0;

  for(int i=0;i<3;i++){

    tmp=s.substr(3*i,2);

    int val=unit[i]*atoi(tmp.c_str());

    res+=val;

  }

  return res;

}



void makeEvent(string start,string arrival){

  int st=getTime(start);

  int at=getTime(arrival);

  train.push_back(make_pair(st,1));

  train.push_back(make_pair(at,0));

}



int main(){

  int n;

  while(cin>>n,n){

    train.clear();

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

    string start,arrival;

    cin>>start>>arrival;

    makeEvent(start,arrival);

    }

    int ans=0,tmp=0;

    sort(train.begin(), train.end());

    for(pii i:train){

      if(i.second==1){

	tmp++;

      }else{

	tmp--;

      }

      ans=max(tmp,ans);

    }

    cout << ans << endl;

  }

  return 0;

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



using namespace std;



typedef long long ll;



int main(){



  int q;

  cin >> q;

  ll ans = 0;

  while(q--){

    ll p,n;

    char c;

    cin >> p >> c >> n;

    if(c == ')') ans -= n;

    if(c == '(') ans += n;

    if(ans == 0) cout << "Yes" << endl;

    else cout << "No" << endl;

  }

  return 0;

}

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



using namespace std;



typedef long long ll;



int main(){



  int q;

  scanf("%d",&q);

  ll ans = 0;

  while(q--){

    int p,n;

    char c;

    scanf("%d %c %d",&p,&c,&n);

    if(c == ')') ans -= n;

    else ans += n;

    if(ans == 0) printf("Yes\n");

    else printf("No\n");

  }

  return 0;

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

using namespace std;

typedef long long ll;

const int N=1505,p=1000000007;

int read(){

	int f=1,g=0;char ch=getchar();

	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;

	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';

	return f*g;

}

int n,a[N][N],s[N][N],l[N][N],r[N][N];

ll ans;

char ch[N];

void del(int x,int y){

	for (int i=y;i<=n;i++) s[x][i]-=a[x][y];

	a[x][y]=0;

	if ((a[x][y+1])&&(!a[x-1][y+1])) del(x,y+1);

	if ((a[x+1][y])&&(!a[x+1][y-1])) del(x+1,y);

}

void chkmin(int &x,int y){if (x>y) x=y;}

void chkmax(int &x,int y){if (x<y) x=y;}

int main(){

	n=read();

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

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

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

		a[i][j]=(ch[j]=='#') ? 0 : (ch[j]-'0'),s[i][j]=s[i][j-1]+a[i][j];

	}

	memset(l,0x3f,sizeof(l));

	for (int i=n;i;i--)

	for (int j=n;j;j--)

	if (a[i][j]){

		int t=-a[i][j];

		l[j][i]=r[j][i]=j;

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

			chkmin(l[j][x],l[j+1][x]);chkmax(r[j][x],r[j+1][x]);

			if (l[j][x]<=r[j][x]) t+=s[x][r[j][x]]-s[x][l[j][x]-1];

		}

		ans+=a[i][j]*t;

		if (a[i-1][j]+a[i][j-1]==0) del(i,j);

	}

	else{memset(l[j]+i,0x3f,(n-i+1)*4);memset(r[j]+i,0,(n-i+1)*4);}

	printf("%lld\n",ans);

	return 0;

}

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

using namespace std;

typedef long long ll;

const int N=1505,p=1000000007;

int read(){

	int f=1,g=0;char ch=getchar();

	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;

	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';

	return f*g;

}

int n;

typedef unsigned short us;

us a[N][N],s[N][N],l[N][N],r[N][N];

ll ans;

char ch[N];

void del(int x,int y){

	for (int i=y;i<=n;i++) s[x][i]-=a[x][y];

	a[x][y]=0;

	if ((a[x][y+1])&&(!a[x-1][y+1])) del(x,y+1);

	if ((a[x+1][y])&&(!a[x+1][y-1])) del(x+1,y);

}

inline void chkmin(us &x,us y){if (x>y) x=y;}

inline void chkmax(us &x,us y){if (x<y) x=y;}

int main(){

	n=read();

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

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

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

		a[i][j]=(ch[j]=='#') ? 0 : (ch[j]-'0'),s[i][j]=s[i][j-1]+a[i][j];

	}

	memset(l,0x3f,sizeof(l));

	for (int i=n;i;i--)

	for (int j=n;j;j--)

	if (a[i][j]){

		int t=-a[i][j];

		l[j][i]=r[j][i]=j;

		if (a[i][j+1]) for (int x=i;x<=n;x++){

			chkmin(l[j][x],l[j+1][x]);chkmax(r[j][x],r[j+1][x]);

			if (l[j][x]<=r[j][x]) t+=s[x][r[j][x]]-s[x][l[j][x]-1];else break;

		}

		else for (int x=i;(x<=n)&&(l[j][x]<=r[j][x]);x++)

			t+=s[x][r[j][x]]-s[x][l[j][x]-1];

		ans+=a[i][j]*t;

		if (a[i-1][j]+a[i][j-1]==0) del(i,j);

	}

	else{memset(l[j]+i,0x3f,(n-i+1)*2);memset(r[j]+i,0,(n-i+1)*2);}

	printf("%lld\n",ans);

	return 0;

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

using namespace std;

typedef long long ll;

const int N=1505,p=1000000007;

int read(){

	int f=1,g=0;char ch=getchar();

	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;

	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';

	return f*g;

}

int n,a[N][N],s[N][N],l[N][N],r[N][N];

ll ans;

char ch[N];

void del(int x,int y){

	for (int i=y;i<=n;i++) s[x][i]-=a[x][y];

	a[x][y]=0;

	if ((a[x][y+1])&&(!a[x-1][y+1])) del(x,y+1);

	if ((a[x+1][y])&&(!a[x+1][y-1])) del(x+1,y);

}

void chkmin(int &x,int y){if (x>y) x=y;}

void chkmax(int &x,int y){if (x<y) x=y;}

int main(){

	n=read();

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

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

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

		a[i][j]=(ch[j]=='#') ? 0 : (ch[j]-'0'),s[i][j]=s[i][j-1]+a[i][j];

	}

	memset(l,0x3f,sizeof(l));

	for (int i=n;i;i--)

	for (int j=n;j;j--)

	if (a[i][j]){

		int t=-a[i][j];

		l[j][i]=r[j][i]=j;

		if (a[i][j+1]) for (int x=i;x<=n;x++){

			chkmin(l[j][x],l[j+1][x]);chkmax(r[j][x],r[j+1][x]);

			if (l[j][x]<=r[j][x]) t+=s[x][r[j][x]]-s[x][l[j][x]-1];else break;

		}

		else for (int x=i;(x<=n)&&(l[j][x]<=r[j][x]);x++)

			t+=s[x][r[j][x]]-s[x][l[j][x]-1];

		ans+=a[i][j]*t;

		if (a[i-1][j]+a[i][j-1]==0) del(i,j);

	}

	else{memset(l[j]+i,0x3f,(n-i+1)*4);memset(r[j]+i,0,(n-i+1)*4);}

	printf("%lld\n",ans);

	return 0;

}

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

using namespace std;

typedef long long ll;

const int N=1505,p=1000000007;

int read(){

	int f=1,g=0;char ch=getchar();

	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;

	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';

	return f*g;

}

int n;

typedef unsigned short us;

us a[N][N],s[N][N],l[N][N],r[N][N];

ll ans;

char ch[N];

void del(int x,int y){

	for (int i=y;i<=n;i++) s[x][i]-=a[x][y];

	a[x][y]=0;

	if ((a[x][y+1])&&(!a[x-1][y+1])) del(x,y+1);

	if ((a[x+1][y])&&(!a[x+1][y-1])) del(x+1,y);

}

inline void chkmin(us &x,us y){if (x>y) x=y;}

inline void chkmax(us &x,us y){if (x<y) x=y;}

int main(){

	n=read();

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

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

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

		a[i][j]=(ch[j]=='#') ? 0 : (ch[j]-'0'),s[i][j]=s[i][j-1]+a[i][j];

	}

	memset(l,0x3f,sizeof(l));

	for (int i=n;i;i--)

	for (int j=n;j;j--)

	if (a[i][j]){

		int t=-a[i][j];

		l[j][i]=r[j][i]=j;

		if (a[i][j+1]) for (int x=i;x<=n;x++){

			chkmin(l[j][x],l[j+1][x]);chkmax(r[j][x],r[j+1][x]);

			if (l[j][x]<=r[j][x]) t+=s[x][r[j][x]]-s[x][l[j][x]-1];else break;

		}

		else for (int x=i;(x<=n)&&(l[j][x]<=r[j][x]);x++)

			t+=s[x][r[j][x]]-s[x][l[j][x]-1];

		ans+=a[i][j]*t;

		if (a[i-1][j]+a[i][j-1]==0) del(i,j);

	}

	else{memset(l[j]+i,0x3f,(n-i+1)*2);memset(r[j]+i,0,(n-i+1)*2);}

	printf("%lld\n",ans);

	return 0;

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

using namespace std;

typedef long long ll;

const int N=1505,p=1000000007;

int read(){

	int f=1,g=0;char ch=getchar();

	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;

	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';

	return f*g;

}

int n,a[N][N],s[N][N],l[N][N],r[N][N];

ll ans;

char ch[N];

void del(int x,int y){

	for (int i=y;i<=n;i++) s[x][i]-=a[x][y];

	a[x][y]=0;

	if ((a[x][y+1])&&(!a[x-1][y+1])) del(x,y+1);

	if ((a[x+1][y])&&(!a[x+1][y-1])) del(x+1,y);

}

void chkmin(int &x,int y){if (x>y) x=y;}

void chkmax(int &x,int y){if (x<y) x=y;}

int main(){

	n=read();

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

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

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

		a[i][j]=(ch[j]=='#') ? 0 : (ch[j]-'0'),s[i][j]=s[i][j-1]+a[i][j];

	}

	memset(l,0x3f,sizeof(l));

	for (int i=n;i;i--)

	for (int j=n;j;j--)

	if (a[i][j]){

		int t=-a[i][j];

		l[j][i]=r[j][i]=j;

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

			chkmin(l[j][x],l[j+1][x]);chkmax(r[j][x],r[j+1][x]);

			if (l[j][x]<=r[j][x]) t+=s[x][r[j][x]]-s[x][l[j][x]-1];

		}

		ans+=a[i][j]*t;

		if (a[i-1][j]+a[i][j-1]==0) del(i,j);

	}

	else{memset(l[j]+i,0x3f,(n-i+1)*4);memset(r[j]+i,0,(n-i+1)*4);}

	printf("%lld\n",ans);

	return 0;

}

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

using namespace std;

typedef long long ll;

const int N=1505,p=1000000007;

int read(){

	int f=1,g=0;char ch=getchar();

	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;

	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';

	return f*g;

}

int n,f[N][N];

typedef unsigned short us;

us a[N][N],l[N][N],r[N][N];

ll ans;

char ch[N];

inline void chkmin(us &x,us y){if (x>y) x=y;}

inline void chkmax(us &x,us y){if (x<y) x=y;}

int main(){

	n=read();

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

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

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

		a[i][j]=(ch[j]=='#') ? 0 : (ch[j]-'0');

	}

	memset(l,0x3f,sizeof(l));

	for (int i=n;i;i--)

	for (int j=n;j;j--)

	if (a[i][j]){

		int t=f[i+1][j]+f[i][j+1];

		if (!a[i][j+1]){l[j][i]=r[j][i]=j;}

		else if (!a[i+1][j]){

			memcpy(l[j]+i,l[j+1]+i,(n-i+1)*2);

			memcpy(r[j]+i,r[j+1]+i,(n-i+1)*2);

			l[j][i]=j;

		}

		else{

			l[j][i]=j;r[j][i]=r[j+1][i];

			us las=0;

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

				if ((l[j+1][x]<=r[j][x])&&(las<l[j+1][x])) t-=f[x][l[j+1][x]];

				chkmax(las,r[j][x]);

				chkmin(l[j][x],l[j+1][x]);chkmax(r[j][x],r[j+1][x]);

			}

		}

		ans+=a[i][j]*t;

		f[i][j]=a[i][j]+t;

	}

	else{memset(l[j]+i,0x3f,(n-i+1)*2);memset(r[j]+i,0,(n-i+1)*2);}

	printf("%lld\n",ans);

	return 0;

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

using namespace std;

typedef long long ll;

const int N=1505,p=1000000007;

int read(){

	int f=1,g=0;char ch=getchar();

	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;

	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';

	return f*g;

}

int n,a[N][N],s[N][N],l[N][N],r[N][N];

ll ans;

char ch[N];

void del(int x,int y){

	for (int i=y;i<=n;i++) s[x][i]-=a[x][y];

	a[x][y]=0;

	if ((a[x][y+1])&&(!a[x-1][y+1])) del(x,y+1);

	if ((a[x+1][y])&&(!a[x+1][y-1])) del(x+1,y);

}

void chkmin(int &x,int y){if (x>y) x=y;}

void chkmax(int &x,int y){if (x<y) x=y;}

int main(){

	n=read();

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

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

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

		a[i][j]=(ch[j]=='#') ? 0 : (ch[j]-'0'),s[i][j]=s[i][j-1]+a[i][j];

	}

	memset(l,0x3f,sizeof(l));

	for (int i=n;i;i--)

	for (int j=n;j;j--)

	if (a[i][j]){

		int t=-a[i][j];

		l[j][i]=r[j][i]=j;

		if (a[i][j+1]) for (int x=i;x<=n;x++){

			chkmin(l[j][x],l[j+1][x]);chkmax(r[j][x],r[j+1][x]);

			if (l[j][x]<=r[j][x]) t+=s[x][r[j][x]]-s[x][l[j][x]-1];else break;

		}

		else for (int x=i;(x<=n)&&(l[j][x]<=r[j][x]);x++)

			t+=s[x][r[j][x]]-s[x][l[j][x]-1];

		ans+=a[i][j]*t;

		if (a[i-1][j]+a[i][j-1]==0) del(i,j);

	}

	else{memset(l[j]+i,0x3f,(n-i+1)*4);memset(r[j]+i,0,(n-i+1)*4);}

	printf("%lld\n",ans);

	return 0;

}

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

using namespace std;

typedef long long ll;

const int N=1505,p=1000000007;

int read(){

	int f=1,g=0;char ch=getchar();

	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;

	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';

	return f*g;

}

int n,f[N][N];

typedef unsigned short us;

us a[N][N],l[N][N],r[N][N];

ll ans;

char ch[N];

inline void chkmin(us &x,us y){if (x>y) x=y;}

inline void chkmax(us &x,us y){if (x<y) x=y;}

int main(){

	n=read();

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

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

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

		a[i][j]=(ch[j]=='#') ? 0 : (ch[j]-'0');

	}

	memset(l,0x3f,sizeof(l));

	for (int i=n;i;i--)

	for (int j=n;j;j--)

	if (a[i][j]){

		int t=f[i+1][j]+f[i][j+1];

		if (!a[i][j+1]){l[j][i]=r[j][i]=j;}

		else if (!a[i+1][j]){

			memcpy(l[j]+i,l[j+1]+i,(n-i+1)*2);

			memcpy(r[j]+i,r[j+1]+i,(n-i+1)*2);

			l[j][i]=j;

		}

		else{

			l[j][i]=j;r[j][i]=r[j+1][i];

			us las=0;

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

				if ((l[j+1][x]<=r[j][x])&&(las<l[j+1][x])) t-=f[x][l[j+1][x]];

				chkmax(las,r[j][x]);

				chkmin(l[j][x],l[j+1][x]);chkmax(r[j][x],r[j+1][x]);

			}

		}

		ans+=a[i][j]*t;

		f[i][j]=a[i][j]+t;

	}

	else{memset(l[j]+i,0x3f,(n-i+1)*2);memset(r[j]+i,0,(n-i+1)*2);}

	printf("%lld\n",ans);

	return 0;

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

using namespace std;

typedef long long ll;

const int N=1505,p=1000000007;

int read(){

	int f=1,g=0;char ch=getchar();

	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;

	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';

	return f*g;

}

int n,a[N][N],s[N][N],l[N][N],r[N][N];

ll ans;

char ch[N];

void del(int x,int y){

	for (int i=y;i<=n;i++) s[x][i]-=a[x][y];

	a[x][y]=0;

	if ((a[x][y+1])&&(!a[x-1][y+1])) del(x,y+1);

	if ((a[x+1][y])&&(!a[x+1][y-1])) del(x+1,y);

}

void chkmin(int &x,int y){if (x>y) x=y;}

void chkmax(int &x,int y){if (x<y) x=y;}

int main(){

	n=read();

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

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

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

		a[i][j]=(ch[j]=='#') ? 0 : (ch[j]-'0'),s[i][j]=s[i][j-1]+a[i][j];

	}

	memset(l,0x3f,sizeof(l));

	for (int i=n;i;i--)

	for (int j=n;j;j--)

	if (a[i][j]){

		int t=-a[i][j];

		l[j][i]=r[j][i]=j;

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

			chkmin(l[j][x],l[j+1][x]);chkmax(r[j][x],r[j+1][x]);

			if (l[j][x]<=r[j][x]) t+=s[x][r[j][x]]-s[x][l[j][x]-1];

		}

		ans+=a[i][j]*t;

		if (a[i-1][j]+a[i][j-1]==0) del(i,j);

	}

	else{memset(l[j]+i,0x3f,(n-i+1)*4);memset(r[j]+i,0,(n-i+1)*4);}

	printf("%lld\n",ans);

	return 0;

}

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

using namespace std;

typedef long long ll;

const int N=1505,p=1000000007;

int read(){

	int f=1,g=0;char ch=getchar();

	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;

	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';

	return f*g;

}

int n,f[N][N],d[N][N];

typedef unsigned short us;

us a[N][N],l[N][N],r[N][N];

ll ans;

char ch[N];

inline void chkmin(us &x,us y){if (x>y) x=y;}

inline void chkmax(us &x,us y){if (x<y) x=y;}

int main(){

	n=read();

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

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

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

		a[i][j]=(ch[j]=='#') ? 0 : (ch[j]-'0');

	}

	memset(l,0x3f,sizeof(l));

	for (int i=n;i;i--)

	for (int j=n;j;j--)

	if (a[i][j]){

		int t=f[i+1][j]+f[i][j+1];

		d[i][j]=max(max(d[i][j+1],d[i+1][j]),i);

		if (!a[i][j+1]){l[j][i]=r[j][i]=j;}

		else if (!a[i+1][j]){

			memcpy(l[j]+i,l[j+1]+i,(n-i+1)*2);

			memcpy(r[j]+i,r[j+1]+i,(n-i+1)*2);

			l[j][i]=j;

		}

		else{

			l[j][i]=j;r[j][i]=r[j+1][i];

			us las=0;

			for (int x=i+1;x<=d[i][j];x++){

				if ((l[j+1][x]<=r[j][x])&&(las<l[j+1][x])) t-=f[x][l[j+1][x]];

				chkmax(las,r[j][x]);

				chkmin(l[j][x],l[j+1][x]);chkmax(r[j][x],r[j+1][x]);

			}

		}

		ans+=a[i][j]*t;

		f[i][j]=a[i][j]+t;

	}

	else{memset(l[j]+i,0x3f,(n-i+1)*2);memset(r[j]+i,0,(n-i+1)*2);}

	printf("%lld\n",ans);

	return 0;

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

using namespace std;

typedef long long ll;

const int N=1505,p=1000000007;

int read(){

	int f=1,g=0;char ch=getchar();

	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;

	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';

	return f*g;

}

int n,a[N][N],s[N][N],l[N][N],r[N][N];

ll ans;

char ch[N];

void del(int x,int y){

	for (int i=y;i<=n;i++) s[x][i]-=a[x][y];

	a[x][y]=0;

	if ((a[x][y+1])&&(!a[x-1][y+1])) del(x,y+1);

	if ((a[x+1][y])&&(!a[x+1][y-1])) del(x+1,y);

}

void chkmin(int &x,int y){if (x>y) x=y;}

void chkmax(int &x,int y){if (x<y) x=y;}

int main(){

	n=read();

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

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

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

		a[i][j]=(ch[j]=='#') ? 0 : (ch[j]-'0'),s[i][j]=s[i][j-1]+a[i][j];

	}

	memset(l,0x3f,sizeof(l));

	for (int i=n;i;i--)

	for (int j=n;j;j--)

	if (a[i][j]){

		int t=-a[i][j];

		l[j][i]=r[j][i]=j;

		if (a[i][j+1]) for (int x=i;x<=n;x++){

			chkmin(l[j][x],l[j+1][x]);chkmax(r[j][x],r[j+1][x]);

			if (l[j][x]<=r[j][x]) t+=s[x][r[j][x]]-s[x][l[j][x]-1];else break;

		}

		else for (int x=i;(x<=n)&&(l[j][x]<=r[j][x]);x++)

			t+=s[x][r[j][x]]-s[x][l[j][x]-1];

		ans+=a[i][j]*t;

		if (a[i-1][j]+a[i][j-1]==0) del(i,j);

	}

	else{memset(l[j]+i,0x3f,(n-i+1)*4);memset(r[j]+i,0,(n-i+1)*4);}

	printf("%lld\n",ans);

	return 0;

}

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

using namespace std;

typedef long long ll;

const int N=1505,p=1000000007;

int read(){

	int f=1,g=0;char ch=getchar();

	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;

	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';

	return f*g;

}

int n,f[N][N],d[N][N];

typedef unsigned short us;

us a[N][N],l[N][N],r[N][N];

ll ans;

char ch[N];

inline void chkmin(us &x,us y){if (x>y) x=y;}

inline void chkmax(us &x,us y){if (x<y) x=y;}

int main(){

	n=read();

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

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

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

		a[i][j]=(ch[j]=='#') ? 0 : (ch[j]-'0');

	}

	memset(l,0x3f,sizeof(l));

	for (int i=n;i;i--)

	for (int j=n;j;j--)

	if (a[i][j]){

		int t=f[i+1][j]+f[i][j+1];

		d[i][j]=max(max(d[i][j+1],d[i+1][j]),i);

		if (!a[i][j+1]){l[j][i]=r[j][i]=j;}

		else if (!a[i+1][j]){

			memcpy(l[j]+i,l[j+1]+i,(n-i+1)*2);

			memcpy(r[j]+i,r[j+1]+i,(n-i+1)*2);

			l[j][i]=j;

		}

		else{

			l[j][i]=j;r[j][i]=r[j+1][i];

			us las=0;

			for (int x=i+1;x<=d[i][j];x++){

				if ((l[j+1][x]<=r[j][x])&&(las<l[j+1][x])) t-=f[x][l[j+1][x]];

				chkmax(las,r[j][x]);

				chkmin(l[j][x],l[j+1][x]);chkmax(r[j][x],r[j+1][x]);

			}

		}

		ans+=a[i][j]*t;

		f[i][j]=a[i][j]+t;

	}

	else{memset(l[j]+i,0x3f,(n-i+1)*2);memset(r[j]+i,0,(n-i+1)*2);}

	printf("%lld\n",ans);

	return 0;

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

#define ll long long



using namespace std;



ll n,k,a[100010],ans;



int main()

{

	scanf("%lld%lld",&n,&k);

	for(int i=1; i<=n; i++)scanf("%lld",&a[i]);

	ans=0x3f3f3f3f;

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

	{

		ll l=a[i],r=a[i+k-1];

		if(l*r>0)ans=min(ans,max(abs(l),abs(r)));

		else ans=min(ans,r-l+min(abs(l),abs(r)));

	}

	printf("%lld",ans);

	return 0;

}

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

#include<cstring>

#include<algorithm>

#include<cmath>

#define MN 100005

using namespace std;

int n,ans=0x3f3f3f3f,a[MN],k;

int main(){

	scanf("%d%d",&n,&k);

	for(int i=1;i<=n;i++)scanf("%d",&a[i]);

	for(int l=1;l+k-1<=n;l++){

		if(1ll*a[l]*a[l+k-1]>=0)ans=min(ans,max(abs(a[l+k-1]),abs(a[l])));

		else ans=min(ans,abs(a[l])+abs(a[l+k-1])+min(abs(a[l]),abs(a[l+k-1])));

	}printf("%d\n",ans);

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

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#define int long long

using namespace std;



const int N=100000+50;

int n,m,a[N],ans=1e18;



inline int read(){

	int x=0,f=1;char ch;

	for(ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')f=-1;

	for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-'0';

	return x*f;

}



signed main(){

	n=read(),m=read();

	for(int i=1;i<=n;++i)a[i]=read();

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

		int j=i+m-1;

		if(a[i]>=0)ans=min(ans,a[j]);

		else if(a[j]<=0)ans=min(ans,-a[i]);

		else ans=min(ans,a[j]-a[i]+min(a[j],-a[i]));

	}

	printf("%lld\n",ans);return 0;

}

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

#include<cstring>

#include<algorithm>

#include<cmath>

#define MN 100005

using namespace std;

int n,ans=0x3f3f3f3f,a[MN],k;

int main(){

	scanf("%d%d",&n,&k);

	for(int i=1;i<=n;i++)scanf("%d",&a[i]);

	for(int l=1;l+k-1<=n;l++){

		if(1ll*a[l]*a[l+k-1]>=0)ans=min(ans,max(abs(a[l+k-1]),abs(a[l])));

		else ans=min(ans,abs(a[l])+abs(a[l+k-1])+min(abs(a[l]),abs(a[l+k-1])));

	}printf("%d\n",ans);

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

#define ll long long

using namespace std;

const int INF=0x3f3f3f3f;

ll n,k,a[100010],ans=INF;

int main()

{

    cin>>n>>k;

    for(int i=0;i<n;i++) cin>>a[i];

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

        ll l=a[i],r=a[i+k-1];

        if(l*r>0) ans=min(ans,max(abs(l),abs(r)));

        else ans=min(ans,abs(l)+abs(r)+min(abs(l),abs(r)));

    }

    cout<<ans<<endl;

    return 0;

}


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

#include<cstring>

#include<algorithm>

#include<cmath>

#define MN 100005

using namespace std;

int n,ans=0x3f3f3f3f,a[MN],k;

int main(){

	scanf("%d%d",&n,&k);

	for(int i=1;i<=n;i++)scanf("%d",&a[i]);

	for(int l=1;l+k-1<=n;l++){

		if(1ll*a[l]*a[l+k-1]>=0)ans=min(ans,max(abs(a[l+k-1]),abs(a[l])));

		else ans=min(ans,abs(a[l])+abs(a[l+k-1])+min(abs(a[l]),abs(a[l+k-1])));

	}printf("%d\n",ans);

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

using namespace std;

typedef long long ll;

typedef long double ld;

const int MOD = (int)1e9 + 7;

const int MAXN = (int)1e5 + 7;

const int infint = (int)1e9;

ll a[MAXN], n, k;

int main()

{

	ios::sync_with_stdio(false);

	cin.tie(0); cout.tie(0);

	cin >> n >> k;

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

		cin >> a[i];

	ll g = -1;

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

	{

		ll ans = abs(a[i] - 0) + abs(a[i] - a[i + k - 1]);

		ll ans2 = abs(a[i + k - 1] - 0) + abs(a[i] - a[i + k - 1]);

		ans = min(ans, ans2);

		if(g == -1 || ans < g)

			g = ans;

	}

	cout << g;

}

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

#include<cstring>

#include<algorithm>

#include<cmath>

#define MN 100005

using namespace std;

int n,ans=0x3f3f3f3f,a[MN],k;

int main(){

	scanf("%d%d",&n,&k);

	for(int i=1;i<=n;i++)scanf("%d",&a[i]);

	for(int l=1;l+k-1<=n;l++){

		if(1ll*a[l]*a[l+k-1]>=0)ans=min(ans,max(abs(a[l+k-1]),abs(a[l])));

		else ans=min(ans,abs(a[l])+abs(a[l+k-1])+min(abs(a[l]),abs(a[l+k-1])));

	}printf("%d\n",ans);

}