#include <stdio.h>

int grid[300][301];	/* one extra row for Kadane's algorithm */

int main( int argc, char **argv )
{
	int gridid;
	int hs=0;
	int s;
	int y;
	char where[512]="";
	if( argc != 2 ) {
		printf( "syntax: %s <gridid>\n", argv[0] );
		return( 0 );
	}
	gridid=atoi(argv[1]);
	/* Initialise grid including setting columnar sums */
	y=0;
	while( y < 301 ) {
		int x=0;
		while( x < 300 ) {
			if( y == 0 ) {
				/* Add in extra row of zeros at top */
				grid[x][0]=0;
			} else {
				int rackid;
				int n;
				rackid=x+1+10;
				n=rackid*y;
				n+=gridid;
				n*=rackid;
				n=((int)(n/100))%10;
				n-=5;
				/*
				 * Kadane's algorithm
				 * set the cell to be the sum of all cells above it
				 */
				grid[x][y]=n+grid[x][y-1];
			}
			x++;
		}
		y++;
	}
	/* Kadane's 2D algorithm but made easier as for squares */
	s=1;
	while( s <= 300 ) {	/* For part a just do a single iteration of s=3 */
		y=0;
		while( y <= (300-s) ) {
			int n=0;
			int x=0;
			while( x < s ) {
				/* Add up first s columns */
				/* Since each cell now contains the sum of all of the cells above it we can calculate partial column totals with a single subtraction */
				n+=grid[x][y+s]-grid[x][y];
				x++;
			}
			if( n > hs ) {
				sprintf(where, "hs=%d at %d,%d,%d\n", n, x-s+2, y+1, s );
				hs=n;
			}
			while( x < 300 ) {
				/* As we increment the column number (x) */
				/* we add on the new partial column total for the new column on the right */
				n+=grid[x][y+s]-grid[x][y];
				/* and take off the partial column total for the column on the left */
				n-=grid[x-s][y+s]-grid[x-s][y];
				if( n > hs ) {
					sprintf(where, "hs=%d at %d,%d,%d\n", n, x-s+2, y+1, s );
					hs=n;
				}
				x++;
			}
			y++;
		}
		s++;
	}
	printf( "%s", where );
}