/*#include <stdio.h>
typedef struct
{
char sc[100];
int year;
int month;
int day;
int total;
} ymd;
int main()
{
ymd arr[101],temp;
int n,i,j,l;
int kp, zp;
scanf("%d",&n);
for(i=1; i<=n; i++)
{
scanf("%s %d %d %d",arr[i].sc,&arr[i].year,&arr[i].month,&arr[i].day);
arr[i].total = arr[i].year*10000+arr[i].month*100+arr[i].day;
}
for(i=1; i<n; i++)
{
for(j=1; j<=n-i; j++)
{
if(arr[j].total>arr[j+1].total)
{
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
for(i=1; i<=n; i++)
{
kp = i;
zp = i;
for(j=i+1;; j++)
{
if(arr[i].total == arr[j].total)
{
zp = j;
}
else
{
break;
}
}
for(j=kp; j<zp; j++)
{
for(l=kp; l<zp; l++)
{
if(strcmp(arr[l].sc,arr[l+1].sc)>0)
{
temp = arr[l];
arr[l] = arr[l+1];
arr[l+1] = temp;
}
}
}
i = zp;
}
for(i=1; i<=n; i++)
{
printf("%s\n",arr[i].sc);
}
}*/
#include <stdio.h>
int memo[10001][10001];
int f(int N)
{
if
}
int main()
{
scanf("%d"&n)
f(N)
}