#include<stdio.h>
int max(int a,int b) { return a>b?a:b; }
int guillotine(int n, int lar[], int hau[], int uti[], int L, int H)
{ int f[L+1][H+1], l,h,k,x,y;

  for(l=0;l<=L;l++) for(h=0;h<=H;h++) f[l][h]=0;

  for(k=0;k<n;k++) if((l=lar[k])<=L) if((h=hau[k])<=H) f[l][h]=max(f[l][h],uti[k]);

  for(l=0;l<=L;l++) for(h=0;h<=H;h++)
  { x=f[l][h];
    for(k=1;k<=l-k;k++) if((y=f[k][h]+f[l-k][h])>x) x=y;
    for(k=1;k<=h-k;k++) if((y=f[l][k]+f[l][h-k])>x) x=y;
    f[l][h]=x;
  }
  void opt(int l, int h)
  { int x=f[l][h], k;
    for(k=1;k<l;k++) if(f[k][h]+f[l-k][h]==x)
    return printf("%dx%d = %dx%d + %dx%d\n",l,h,k,h,l-k,h),opt(k,h),opt(l-k,h);
    for(k=1;k<h;k++) if(f[l][k]+f[l][h-k]==x)
    return printf("%dx%d = %dx%d + %dx%d\n",l,h,l,k,l,h-k),opt(l,k),opt(l,h-k);
    printf("%dx%d : %d\n",l,h,x);
  }
  return opt(L,H), f[L][H];
}
int main()
{ int lar[]={3,4,5}, hau[]={4,5,6}, uti[]={1,3,5}, u=guillotine(3,lar,hau,uti,40,40);
  printf("%d\n",u);
  return 0;
}