/*在一个确定的时刻，每个点作为endpoints可得多少分
  在下一时刻，每个点作为endpoints可得多少分为：
        dp[i][j][k]=max{dp[x~][y~][k-1]+Mole[x][y][k]}
		    表示以(x~,y~)为起始坐标，i,j为目标坐标，在上一时刻(x~,y~)得到的最多分加上沿路可得到的分；
			取这些可选路线中使第k时刻以(i,j)为目标坐标得到最多分的路线放在dp[i][j][k]
*/
#include<iostream>
#include<cstdio>
using std::max;
const int N=32;
const int T=11;
//可选路线
short north[6][2]={ {0,-1},{0,1},{0,2},{0,3},{0,4},{0,5} };
short south[6][2]={ {0,1},{0,-1},{0,-2},{0,-3},{0,-4},{0,-5} };
short west[6][2]={ {1,0},{-1,0},{-2,0},{-3,0},{-4,0},{-5,0} };
short east[6][2]={ {-1,0},{1,0},{2,0},{3,0},{4,0},{5,0} };
short length1[5]={1,2,3,4,5};

short northEast[4][2]={ {-1,-1},{1,1},{2,2},{3,3} };
short southEast[4][2]={ {-1,1},{1,-1},{2,-2},{3,-3} };
short southWest[4][2]={ {1,1},{-1,-1},{-2,-2},{-3,-3} };
short northWest[4][2]={ {1,-1},{-1,1},{-2,2},{-3,3} };
short length2[5]={0,1,2,2,3};

short northEast1[2][2]={ {-1,-4},{1,4} };
short southEast1[2][2]={ {-1,4},{1,-4} };
short southWest1[2][2]={ {1,4},{-1,-4} };
short northWest1[2][2]={ {1,-4},{-1,4} };

short northEast6[2][2]={ {-4,-1},{4,1} };
short southEast6[2][2]={ {4,-1},{-4,1} };
short southWest6[2][2]={ {4,1},{-4,-1} };
short northWest6[2][2]={ {-4,1},{4,-1} };

short length3[5]={0,0,0,0,1};

short northEast2[2][2]={ {-1,-3},{1,3} };
short southEast2[2][2]={ {-1,3},{1,-3} };
short southWest2[2][2]={ {1,3},{-1,-3} };
short northWest2[2][2]={ {1,-3},{-1,3} };

short northEast5[2][2]={ {-3,-1},{3,1} };
short southEast5[2][2]={ {3,-1},{-3,1} };
short southWest5[2][2]={ {3,1},{-3,-1} };
short northWest5[2][2]={ {-3,1},{3,-1} };

short length4[5]={0,0,0,1,1};

short northEast3[3][2]={ {-1,-2},{1,2},{2,4} };
short southEast3[3][2]={ {-1,2},{1,-2},{2,-4} };
short southWest3[3][2]={ {1,2},{-1,-2},{-2,-4} };
short northWest3[3][2]={ {1,-2},{-1,2},{-2,4} };

short northEast4[3][2]={ {-2,-1},{2,1},{4,2} };
short southEast4[3][2]={ {2,-1},{-2,1},{-4,2} };
short southWest4[3][2]={ {2,1},{-2,-1},{-4,-2} };
short northWest4[3][2]={ {-2,1},{2,-1},{4,-2} };

short length5[5]={0,0,1,1,2};


short northEast7[2][2]={ {-2,-3},{2,3} };
short southEast7[2][2]={ {2,-3},{-2,3} };
short southWest7[2][2]={ {2,3},{-2,-3} };
short northWest7[2][2]={ {-2,3},{2,-3} };

short northEast8[2][2]={ {-3,-2},{3,2} };
short southEast8[2][2]={ {3,-2},{-3,2} };
short southWest8[2][2]={ {3,2},{-3,-2} };
short northWest8[2][2]={ {-3,2},{3,-2} };

short length6[5]={0,0,0,1,1};

short northEast9[2][2]={ {-3,-4},{3,4} };
short southEast9[2][2]={ {3,-4},{-3,4} };
short southWest9[2][2]={ {3,4},{-3,-4} };
short northWest9[2][2]={ {-3,4},{3,-4} };

short northEast10[2][2]={ {-4,-3},{4,3} };
short southEast10[2][2]={ {4,-3},{-4,3} };
short southWest10[2][2]={ {4,3},{-4,-3} };
short northWest10[2][2]={ {-4,3},{4,-3} };

short length7[5]={0,0,0,0,1};
//每个时刻老鼠出现的表
short Mole[N][N][T];
//存每个时刻每个点作为目标点可得的最多分
int dp[N][N][T];
int n,d,m;
int maxt;
void init()//初始化
{
	memset(Mole,0,sizeof(Mole));
	memset(dp,0,sizeof(dp));
	maxt=0;
}
void input()
{
	int x,y,t;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&t);
		Mole[x+5][y+5][t]=1;
		if(maxt<t)
			maxt=t;
	}
}
int getMax(int x,int y,int k)//找出以(x,y)为endpoints可得的最多分
{
	int temp;
	int result=0;
	int i;
	int posX,posY;
	if(length1[d-1]>0)
	{
		for(i=1;i<=length1[d-1];i++)
		{
			posX=x+north[i][0];
			posY=y+north[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=north[0][0];
					posY+=north[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}

		for(i=1;i<=length1[d-1];i++)
		{
			posX=x+south[i][0];
			posY=y+south[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=south[0][0];
					posY+=south[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}

		for(i=1;i<=length1[d-1];i++)
		{
			posX=x+east[i][0];
			posY=y+east[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=east[0][0];
					posY+=east[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}

		for(i=1;i<=length1[d-1];i++)
		{
			posX=x+west[i][0];
			posY=y+west[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=west[0][0];
					posY+=west[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}

	}

	if(length2[d-1]>0)
	{
		for(i=1;i<=length2[d-1];i++)
		{
			posX=x+northEast[i][0];
			posY=y+northEast[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=northEast[0][0];
					posY+=northEast[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}

		for(i=1;i<=length2[d-1];i++)
		{
			posX=x+southEast[i][0];
			posY=y+southEast[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=southEast[0][0];
					posY+=southEast[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}

		for(i=1;i<=length2[d-1];i++)
		{
			posX=x+southWest[i][0];
			posY=y+southWest[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=southWest[0][0];
					posY+=southWest[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}

		for(i=1;i<=length2[d-1];i++)
		{
			posX=x+northWest[i][0];
			posY=y+northWest[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=northWest[0][0];
					posY+=northWest[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}

	}
	if(length3[d-1]>0)
	{
		for(i=1;i<=length3[d-1];i++)
		{
			posX=x+northEast1[i][0];
			posY=y+northEast1[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=northEast1[0][0];
					posY+=northEast1[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}
		for(i=1;i<=length3[d-1];i++)
		{
			posX=x+northEast6[i][0];
			posY=y+northEast6[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=northEast6[0][0];
					posY+=northEast6[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}

		for(i=1;i<=length3[d-1];i++)
		{
			posX=x+southEast1[i][0];
			posY=y+southEast1[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=southEast1[0][0];
					posY+=southEast1[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}
		for(i=1;i<=length3[d-1];i++)
		{
			posX=x+southEast6[i][0];
			posY=y+southEast6[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=southEast6[0][0];
					posY+=southEast6[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}

		for(i=1;i<=length3[d-1];i++)
		{
			posX=x+southWest1[i][0];
			posY=y+southWest1[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=southWest1[0][0];
					posY+=southWest1[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}
		for(i=1;i<=length3[d-1];i++)
		{
			posX=x+southWest6[i][0];
			posY=y+southWest6[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=southWest6[0][0];
					posY+=southWest6[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}

		for(i=1;i<=length3[d-1];i++)
		{
			posX=x+northWest1[i][0];
			posY=y+northWest1[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=northWest1[0][0];
					posY+=northWest1[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}
		for(i=1;i<=length3[d-1];i++)
		{
			posX=x+northWest6[i][0];
			posY=y+northWest6[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=northWest6[0][0];
					posY+=northWest6[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}
	}
	if(length4[d-1]>0)
	{
		for(i=1;i<=length4[d-1];i++)
		{
			posX=x+northEast2[i][0];
			posY=y+northEast2[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=northEast2[0][0];
					posY+=northEast2[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}
		for(i=1;i<=length4[d-1];i++)
		{
			posX=x+northEast5[i][0];
			posY=y+northEast5[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=northEast5[0][0];
					posY+=northEast5[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}

		for(i=1;i<=length4[d-1];i++)
		{
			posX=x+southEast2[i][0];
			posY=y+southEast2[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=southEast2[0][0];
					posY+=southEast2[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}
		for(i=1;i<=length4[d-1];i++)
		{
			posX=x+southEast5[i][0];
			posY=y+southEast5[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=southEast5[0][0];
					posY+=southEast5[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}

		for(i=1;i<=length4[d-1];i++)
		{
			posX=x+southWest2[i][0];
			posY=y+southWest2[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=southWest2[0][0];
					posY+=southWest2[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}
		for(i=1;i<=length4[d-1];i++)
		{
			posX=x+southWest5[i][0];
			posY=y+southWest5[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=southWest5[0][0];
					posY+=southWest5[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}

		for(i=1;i<=length4[d-1];i++)
		{
			posX=x+northWest2[i][0];
			posY=y+northWest2[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=northWest2[0][0];
					posY+=northWest2[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}
		for(i=1;i<=length4[d-1];i++)
		{
			posX=x+northWest5[i][0];
			posY=y+northWest5[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=northWest5[0][0];
					posY+=northWest5[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}
	}
	if(length5[d-1]>0)
	{
		for(i=1;i<=length5[d-1];i++)
		{
			posX=x+northEast3[i][0];
			posY=y+northEast3[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=northEast3[0][0];
					posY+=northEast3[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}
		for(i=1;i<=length5[d-1];i++)
		{
			posX=x+northEast4[i][0];
			posY=y+northEast4[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=northEast4[0][0];
					posY+=northEast4[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}

		for(i=1;i<=length5[d-1];i++)
		{
			posX=x+southEast3[i][0];
			posY=y+southEast3[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=southEast3[0][0];
					posY+=southEast3[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}
		for(i=1;i<=length5[d-1];i++)
		{
			posX=x+southEast4[i][0];
			posY=y+southEast4[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=southEast4[0][0];
					posY+=southEast4[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}

		for(i=1;i<=length5[d-1];i++)
		{
			posX=x+southWest3[i][0];
			posY=y+southWest3[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=southWest3[0][0];
					posY+=southWest3[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}
		for(i=1;i<=length5[d-1];i++)
		{
			posX=x+southWest4[i][0];
			posY=y+southWest4[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=southWest4[0][0];
					posY+=southWest4[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}

		for(i=1;i<=length5[d-1];i++)
		{
			posX=x+northWest3[i][0];
			posY=y+northWest3[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=northWest3[0][0];
					posY+=northWest3[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}
		for(i=1;i<=length5[d-1];i++)
		{
			posX=x+northWest4[i][0];
			posY=y+northWest4[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=northWest4[0][0];
					posY+=northWest4[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}
	}
	if(length6[d-1]>0)
	{
		for(i=1;i<=length6[d-1];i++)
		{
			posX=x+northEast7[i][0];
			posY=y+northEast7[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=northEast7[0][0];
					posY+=northEast7[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}
		for(i=1;i<=length6[d-1];i++)
		{
			posX=x+northEast8[i][0];
			posY=y+northEast8[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=northEast8[0][0];
					posY+=northEast8[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}

		for(i=1;i<=length6[d-1];i++)
		{
			posX=x+southEast7[i][0];
			posY=y+southEast7[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=southEast7[0][0];
					posY+=southEast7[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}
		for(i=1;i<=length6[d-1];i++)
		{
			posX=x+southEast8[i][0];
			posY=y+southEast8[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=southEast8[0][0];
					posY+=southEast8[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}

		for(i=1;i<=length6[d-1];i++)
		{
			posX=x+southWest7[i][0];
			posY=y+southWest7[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=southWest7[0][0];
					posY+=southWest7[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}
		for(i=1;i<=length6[d-1];i++)
		{
			posX=x+southWest8[i][0];
			posY=y+southWest8[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=southWest8[0][0];
					posY+=southWest8[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}

		for(i=1;i<=length6[d-1];i++)
		{
			posX=x+northWest7[i][0];
			posY=y+northWest7[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=northWest7[0][0];
					posY+=northWest7[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}
		for(i=1;i<=length6[d-1];i++)
		{
			posX=x+northWest8[i][0];
			posY=y+northWest8[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=northWest8[0][0];
					posY+=northWest8[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}
	}
	if(length7[d-1]>0)
	{
		for(i=1;i<=length7[d-1];i++)
		{
			posX=x+northEast9[i][0];
			posY=y+northEast9[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=northEast9[0][0];
					posY+=northEast9[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}
		for(i=1;i<=length7[d-1];i++)
		{
			posX=x+northEast10[i][0];
			posY=y+northEast10[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=northEast10[0][0];
					posY+=northEast10[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}

		for(i=1;i<=length7[d-1];i++)
		{
			posX=x+southEast9[i][0];
			posY=y+southEast9[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=southEast9[0][0];
					posY+=southEast9[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}
		for(i=1;i<=length7[d-1];i++)
		{
			posX=x+southEast10[i][0];
			posY=y+southEast10[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=southEast10[0][0];
					posY+=southEast10[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}

		for(i=1;i<=length7[d-1];i++)
		{
			posX=x+southWest9[i][0];
			posY=y+southWest9[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=southWest9[0][0];
					posY+=southWest9[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}
		for(i=1;i<=length7[d-1];i++)
		{
			posX=x+southWest10[i][0];
			posY=y+southWest10[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=southWest10[0][0];
					posY+=southWest10[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}

		for(i=1;i<=length7[d-1];i++)
		{
			posX=x+northWest9[i][0];
			posY=y+northWest9[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=northWest9[0][0];
					posY+=northWest9[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}
		for(i=1;i<=length7[d-1];i++)
		{
			posX=x+northWest10[i][0];
			posY=y+northWest10[i][1];
			if((posX>=0 && posX<n) && (posY>=0 && posY<n))
			{
				temp=dp[posX][posY][k-1]+Mole[posX][posY][k];
				while(posX!=x || posY!=y)
				{
					posX+=northWest10[0][0];
					posY+=northWest10[0][1];
					temp+=Mole[posX][posY][k];
				}
				result=temp>result?temp:result;
			}
		}
	}
	return result;
}
void dynamic()//求出一时刻每个点作为目标点可得的最多分，则下一时刻dp[i][j][k]=max{dp[x~][y~][k-1]+Mole[x][y][k]}
{
	int i,j,k;
	for(k=1;k<=maxt;k++)
	{
		for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
			{
				dp[i][j][k]=getMax(i,j,k);
			}
		}
	}
}
int getResult()//从最终时刻中找到最优的结果
{
	int i,j;
	int result=0;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
			if(result<dp[i][j][maxt])
				result=dp[i][j][maxt];
	}
	return result;
}
int main()
{
	while(scanf("%d%d%d",&n,&d,&m),n!=0 || d!=0 || m!=0)
	{
		n+=10;
		init();
		input();
		dynamic();
		printf("%d\n",getResult());
	}
	return 0;
}