#include <stdio.h>

int sq_size;
int max_tile;
int max_max;

#define DEBUG_P(X)
#define DEBUG_P1(X,A) 
#define DEBUG_P3(X,A,B,C)
#define DEBUG_P4(X,A,B,C,D)
#define DO_DEBUG_P4(X,A,B,C,D) fprintf(stderr, X,A,B,C,D)

char field[70][70];

int max = 0;

int do_print = 0;

void try(n, m) int n, m;
{   int nm1 = n - 1,
        i,j;
    int p = 'A' + max_tile - n;

    if (n == 0)
    {   int a,b;

        if (m < max)
            return;

        max = m;
        if (do_print)
        {   printf("max = %d\n", m);
            for (a = 0; a < sq_size; a++)
            {   for (b = 0; b < sq_size; b++)
                    printf("%c", field[a][b]);
                printf("|\n");
            }
            printf("*\n");
            fflush(stdout);
        }
        return;
    }

    if (m < max || max == max_max)
        return;

    for (i = 0; i < sq_size - nm1 && m > max && max != max_max; i++)
    {   for (j = 0; j < sq_size - nm1 && m > max && max != max_max; j++)
        {   int ipn = i + n - 1,
                jpn = j + n - 1;

#define CORNER(i,j) ( (i > 0 ? field[i-1][j] != ' ' : 1) \
                     +(j > 0 ? field[i][j-1] != ' ' : 1) \
                     +(i < sq_size-1 ? field[i+1][j] != ' ' : 1) \
                     +(j < sq_size-1 ? field[i][j+1] != ' ' : 1))

            if (   field[i][j] == ' ' 
                && field[i][jpn] == ' '
                && field[ipn][j] == ' '
                && field[ipn][jpn] == ' '
                && (   CORNER(i,j) > 1
                    || CORNER(i,jpn) > 1
                    || CORNER(ipn,j) > 1
                    || CORNER(ipn,jpn) > 1))
            {   int a,b;

                DEBUG_P4("%*s %d %d\n", max_tile + 1 - n, "", i, j);

                for (a = i; a <= ipn; a++)
	            for (b = j; b <= jpn; b++)
                        field[a][b] = p;

                try(nm1, m);

                for (a = i; a <= ipn; a++)
	            for (b = j; b <= jpn; b++)
                        field[a][b] = ' ';
            }
        }
    }

    try(n - 1, m - n*n);
}

int count(s, t) int s, t;
{   int i, j, l = 0;

    sq_size = s;
    max_tile = t;
    max = 0;

    for (i = 0; i < sq_size; i++)
        for (j = 0; j < sq_size; j++)
            field[i][j] = ' ';
    for (i = 1; i <= max_tile; i++)
        l += i*i;
    max_max = l;

    try(max_tile, l);

    return max;
}


int main(argc, argv) int argc; char *argv[];
{   int i,j,l = 0;

    if (argc < 3)
    {   
        int s, t;

        for (s = 1; s < 40; s++)
        {   printf("%3d | ", s);
            for (t = 1; t <= s; t++)
            {   printf("%5d", count(s, t));
                fflush(stdout);
            }
            printf("\n");
        }
        return 0;
    }
    sq_size = atoi(argv[1]);
    max_tile = atoi(argv[2]);
    do_print = 1;

    for (i = 0; i < sq_size; i++)
        for (j = 0; j < sq_size; j++)
            field[i][j] = ' ';
    for (i = 1; i <= max_tile; i++)
        l += i*i;
    max_max = l;

    try(max_tile, l);

    return 0;
}