#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int min(int a,int b)
{
	if(a<b) return a;
	return b;
}
int main()
{
	//Reading file================================
	FILE* infile, *outfile;
	unsigned char ch,ch2;
	int rows=0,cols=0,max=0;
	int n,m,p,k;
	infile=fopen("image.ppm","r");
	for(n=0;n<3;n++)
	{
		fread(&ch,sizeof(char),1,infile); //P,6,\n
	}
	while(1)
	{
		fread(&ch,sizeof(char),1,infile);
		if(ch==' ') break;
		cols*=10;
		cols+=(ch-'0');
	}
	while(1)
	{
		fread(&ch,sizeof(char),1,infile);
		if(ch=='\n') break;
		rows*=10;
		rows+=(ch-'0');
	}
	while(1)
	{
		fread(&ch,sizeof(char),1,infile);
		if(ch=='\n') break;
		max*=10;
		max+=(ch-'0');
	}
	
	int color[rows][cols][3];
	for(n=0;n<rows;n++)
	{
		for(m=0;m<cols;m++)
		{
			for(p=0;p<3;p++)
			{
				fread(&ch,sizeof(char),1,infile);
				color[n][m][p]=(int)(ch);
			}
		}
	}
	fclose(infile);
	printf("Starting dimensions: %d %d\nNew dimensions: ",rows,cols);
	int newwidth,newheight;
	scanf("%d %d",&newheight,&newwidth);
	//Initialize Arrays
	int gray[rows][cols];	
	int gradient[rows][cols];
	int M[rows][cols];
	int MAXM=0;
	//Horizontal Resizing Loop
	//EXPANDING
	if(newwidth>cols)
	{
		int final[newheight][newwidth];
		
	}
	//SHRINKING
	for(;cols>newwidth;cols--)
	{
		//Grayscale
		for(n=0;n<rows;n++)
	        {
			for(m=0;m<cols;m++)
			{
				gray[n][m]=(color[n][m][0]+color[n][m][1]+color[n][m][2])/3;
			}
		}
		//Gradient Magnitude
		for(n=0;n<rows;n++)
		{
			gradient[n][0]=255;
			gradient[n][cols-1]=255;
		}
		for(n=0;n<cols;n++)
		{
			gradient[0][n]=255;
			gradient[rows-1][n]=255;
		}
		for(n=1;n<rows-1;n++)
		{
			for(m=1;m<cols-1;m++)
			{
				gradient[n][m]=abs(gray[n][m+1]-gray[n][m])/2 + abs(gray[n+1][m]-gray[n][m])/2;
			}
		}
		//Summing Paths
        	for(n=0;n<cols;n++)
        	        M[0][n]=gradient[0][n];
        	for(n=1;n<rows;n++)
        	{
        	        for(m=0;m<cols;m++)
        	        {
        	                if(m==0)
        	                {
        	                        M[n][m]=gradient[n][m]+min(M[n-1][m],M[n-1][m+1]);
        	                }
        	                else if(m==cols-1)
        	                {
        	                        M[n][m]=gradient[n][m]+min(M[n-1][m-1],M[n-1][m]);
        	                }
        	                else
        	                {
        	                        M[n][m]=gradient[n][m]+min(M[n-1][m-1],min(M[n-1][m],M[n-1][m+1]));
        	                }
        	                if(M[n][m]>MAXM) MAXM=M[n][m];
        	        }
        	}
		//Finding minimum path
		int mini=M[rows-1][0];
		int mincol=0;
		for(n=0;n<cols;n++)
		{
			if(M[rows-1][n]<mini)
			{
				mini=M[rows-1][n];
				mincol=n;
			}
		}
		int minpath[rows];
		minpath[rows-1]=mincol;
		for(n=rows-1;n>0;n--)
		{
			if(M[n-1][minpath[n]-1]<=M[n-1][minpath[n]] && M[n-1][minpath[n]-1]<=M[n-1][minpath[n]+1])
			{
				minpath[n-1]=minpath[n]-1;
			}
			if(M[n-1][minpath[n]]<=M[n-1][minpath[n]-1] && M[n-1][minpath[n]]<=M[n-1][minpath[n]+1])
			{
				minpath[n-1]=minpath[n];
			}
			if(M[n-1][minpath[n]+1]<=M[n-1][minpath[n]] && M[n-1][minpath[n]+1]<=M[n-1][minpath[n]-1])
			{
				minpath[n-1]=minpath[n]+1;
			}
		}
		//Removing minimum path
		for(n=0;n<rows;n++)
		{
			for(m=minpath[n];m<cols-1;m++)
			{
				color[n][m][0]=color[n][m+1][0];
				color[n][m][1]=color[n][m+1][1];
				color[n][m][2]=color[n][m+1][2];
			}
		}		
	}


	//Vertical Resizing Loop
	//EXPANDING
	
	//SHRINKING
	for(;rows>newheight;rows--)
	{
		//Grayscale
		for(n=0;n<rows;n++)
	        {
			for(m=0;m<cols;m++)
			{
				gray[n][m]=(color[n][m][0]+color[n][m][1]+color[n][m][2])/3;
			}
		}
		for(n=0;n<rows;n++)
		{
			for(m=0;m<cols;m++)
			{
				if(n==rows-1 || m==cols-1)
				{
					gradient[n][m]=abs(gray[n][m-1]-gray[n][m])/2 + abs(gray[n-1][m]-gray[n][m])/2;
				}
				else
				{
					gradient[n][m]=abs(gray[n][m+1]-gray[n][m])/2 + abs(gray[n+1][m]-gray[n][m])/2;
				}
			}
		}
		//Summing Paths
        	for(n=0;n<rows;n++)
        	        M[n][0]=gradient[n][0];
        	MAXM=0;
		for(n=1;n<cols;n++)
        	{
        	        for(m=0;m<rows;m++)
        	        {
        	                if(m==0)
        	                {
        	                        M[m][n]=gradient[m][n]+min(M[m][n-1],M[m+1][n-1]);
        	                }
        	                else if(m==rows-1)
        	                {
        	                        M[m][n]=gradient[m][n]+min(M[m][n-1],M[m-1][n-1]);
        	                }
        	                else
        	                {
        	                        M[m][n]=gradient[m][n]+min(M[m-1][n-1],min(M[m][n-1],M[m+1][n-1]));
        	                }
        	                if(M[m][n]>MAXM) MAXM=M[m][n];
        	        }
        	}
		if(rows==newheight+1)
		{
			outfile=fopen("M.ppm","w");
        		fprintf(outfile,"P6\n%d %d\n%d\n",cols,rows,max);
        		for(n=0;n<rows;n++)
        		{
        		        for(m=0;m<cols;m++)
        		        {
        		                fprintf(outfile,"%c",M[n][m]*255/MAXM);
        		                fprintf(outfile,"%c",M[n][m]*255/MAXM);
        		                fprintf(outfile,"%c",M[n][m]*255/MAXM);
        		        }
        		}
        		fclose(outfile);
		}
		//Finding minimum path
		int mini=M[0][cols-1];
		int minrow=0;
		for(n=0;n<rows;n++)
		{
			if(M[n][cols-1]<mini)
			{
				mini=M[n][cols-1];
				minrow=n;
				printf("%d   %d\n",minrow,mini);
			}
		}
		int minpath2[cols];
		minpath2[cols-1]=minrow;
		for(n=cols-1;n>0;n--)
		{
			if(M[n-1][minpath2[n]-1]<=M[n-1][minpath2[n]] && M[n-1][minpath2[n]-1]<=M[n-1][minpath2[n]+1])
			{
				minpath2[n-1]=minpath2[n]-1;
			}
			if(M[n-1][minpath2[n]]<=M[n-1][minpath2[n]-1] && M[n-1][minpath2[n]]<=M[n-1][minpath2[n]+1])
			{
				minpath2[n-1]=minpath2[n];
			}
			if(M[n-1][minpath2[n]+1]<=M[n-1][minpath2[n]] && M[n-1][minpath2[n]+1]<=M[n-1][minpath2[n]-1])
			{
				minpath2[n-1]=minpath2[n]+1;
			}
		}
		//Removing minimum path
		for(n=0;n<cols;n++)
		{
			for(m=minpath2[n];m<rows-1;m++)
			{
				color[m][n][0]=color[m+1][n][0];
				color[m][n][1]=color[m+1][n][1];
				color[m][n][2]=color[m+1][n][2];
			}
		}		
	}



	//Final Image
	outfile=fopen("final.ppm","w");
	fprintf(outfile,"P6\n%d %d\n%d\n",newwidth,rows,max);
	for(n=0;n<rows;n++)
	{
		for(m=0;m<newwidth;m++)
		{
			fprintf(outfile,"%c",color[n][m][0]);
			fprintf(outfile,"%c",color[n][m][1]);
			fprintf(outfile,"%c",color[n][m][2]);
		}
	}
	fclose(outfile);
	return 0;
}