#include"stdio.h"
void optimalsearch(int a[],int b[],int n,int m[][6],int s[][6],int w[][6])
{
	for(int i=0;i<=n;i++)
	{
		w[i+1][i]=a[i];
		m[i+1][i]=0;
	}
	for(int r=0;r<n;r++)
		for(int i=1;i<=n-r;i++)
		{
			int j=i+r;
			w[i][j]=w[i][j-1]+a[j]+b[j];
			m[i][j]=m[i+1][j];
			s[i][j]=i;
			for(int k=i+1;k<=j;k++)
			{
				int t=m[i][k-1]+m[k+1][j];
				if(t<m[i][j])
				{
					m[i][j]=t;
					s[i][j]=k;
				}
			}
				m[i][j]+=w[i][j];
			
		}
}
void main()
{
	int a[]={2,1,3,1,1};
	int b[]={0,1,3,2,2};
	int m[6][6]={0};
	int w[6][6]={0};
	int s[6][6]={0};
	optimalsearch(a, b, 4,m,s,w);
	//for(int i=0;i<=4
    printf("%5d%5d\n",m[1][4],s[1][4]);
}