11002

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>

using namespace std;

bool dp[65][65][6005];
int arr[65][65];
int n;

void init()
{
	for(int i=0;i<65;i++)
		for(int j=0;j<65;j++)
		{
			arr[i][j]=0;
			for(int k=0;k<6005;k++)
				dp[i][j][k]=0;
		}
}


int main()
{
	int cnt,tmp,tmp2,val;
	while(scanf("%d",&n),n)
	{
		init();
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=i;j++)
				scanf("%d",&arr[i][j]);
		}
		cnt = n;
		for(int i=n+1;i<=2*n-1;i++)
		{
			cnt-=1;
			for(int j=1;j<=cnt;j++)
			{
				scanf("%d",&arr[i][j]);
			}
		}
		cnt = 0;
		dp[2*n-1][1][ arr[2*n-1][1]+3000 ] = 1;
		for(int i=2*n-1;i>=n+1;i--)
		{
			cnt+=1;
			for(int j=1;j<=cnt;j++)
			{
				for(int k=0;k<6005;k++)
				{
					if(dp[i][j][k]==true)
					{
						tmp = arr[i-1][j];
						val = k+tmp;
						dp[i-1][j][val]=true;
						val = k-tmp;
						dp[i-1][j][val]=true;
						tmp2 = arr[i-1][j+1];
						val = k+tmp2;
						dp[i-1][j+1][val]=true;
						val = k-tmp2;
						dp[i-1][j+1][val]=true;
					}
				}
			}
		}// end of for loop
		cnt=n+1;
		for(int i=n;i>=2;i--)
		{
			cnt-=1;
			for(int j=1;j<=cnt;j++)
			{
				for(int k=0;k<6005;k++)
				{
					if(dp[i][j][k]==true)
					{
						tmp = arr[i-1][j-1];
						tmp2 = arr[i-1][j];
						if(j==1)
						{
							val = k+tmp2;
							dp[i-1][j][val]=true;
							val = k-tmp2;
							dp[i-1][j][val]=true;
						}
						else if(j==cnt)
						{
							val = k+tmp;
							dp[i-1][j-1][val]=true;
							val = k-tmp;
							dp[i-1][j-1][val]=true;
						}
						else
						{
							val = k+tmp;
							dp[i-1][j-1][val]=true;
							val = k-tmp;
							dp[i-1][j-1][val]=true;
							val = k+tmp2;
							dp[i-1][j][val]=true;
							val = k-tmp2;
							dp[i-1][j][val]=true;
						}
					}
				}
			}
		}//end for loop
		int mn = 7000;
		for(int i=3000;i>=0;i--)
		{
			if(dp[1][1][i]==true)
			{
				mn=3000-i;
				break;
			}
		}
		int mx = 7000;
		for(int i=3001;i<6005;i++)
		{
			if(dp[1][1][i]==true)
			{
				mx=i-3000;
				break;
			}
		}
		cout<<(mn<mx?mn:mx)<<"\n";
	}
	return 0;
}