#include <stdio.h>
int p[100]={0,1,5,8,9,10,17,17,20,24,30};
int arr[100];
  int main()
    {
        int i,val;
        val=cut_rod(9);
        printf("%d\n",val);
    }
int cut_rod(int n)
{
    int i,q;
    if(arr[n]>0)
    {
        return arr[n];
    }
    if(n==0)

    {
        return 0;
    }
    else
    {
        q=-9999;
        for(i=1;i<=n;i++)
            q=max(q , p[i]+ cut_rod(n-i));
    }
            arr[i]=q;
            return q;
    }


int max(int a,int b)
{
    if(a>b)
        return a;
    else
        return b;
}