小 E 的房子终于竣工了，现在他要装饰一下房子的内部。
房子的平面图是一个 n*n 的正方形，分为 n*n 个单位面积的格子，但只有 m 个格子可以摆放装饰物。第 i 行第 j 列的格子摆放装饰物可以得到 a_{ij} 的美观度.
如果两个相邻的格子都摆放了装饰物，则总的美观值会下降 x，请你告诉小 E，最大的美观值是多少？
第一行，三个数， n,m,x
接下来 m 行，每行三个数， i,j,a_{ij} ，代表 (i,j) 这个格子可以摆放装饰物并且美观值为 a_{ij} 。
一行，一个数，表示答案。
样例输入
3 4 2 1 1 1 1 2 4 2 2 3 3 3 1
样例输出
6
说明：选择格子（1,2）、（2,2）、（3,3）摆放装饰物，得到美观度=4+3+1-2=6
对于 30% 的数据， 1\leq n,m\leq 3,1 \leq a_{ij},x \leq 100 ；
对于 100% 的数据， 1\leq n,m \leq 10,1\leq a_{ij},x \leq 10^{12} 。
【子集枚举】