暂无测试数据。

小 E 的房子终于竣工了，现在他要装饰一下房子的内部。

房子的平面图是一个 $n*n$ 的正方形，分为 $n*n$ 个单位面积的格子，每个格子里都可以摆放一个装饰物，第 $i$ 行第 $j$ 列的格子摆放装饰物可以得到 $a_{ij}$ 的美观度，但只有 $m$ 个格子可以摆放装饰物。

如果两个相邻的格子都摆放了装饰物，则总的美观值会下降 $x$,请你告诉小 E，最大的美观值是多少？

输入格式

第一行，三个数，$n,m,x$

接下来 $m$ 行，每行三个数，$x',y',a_{x'y'}$，代表 $(x',y')$ 这个格子可以摆放装饰物并且美观值为 $a_{x'y'}$。

输出格式

一行，一个数，表示答案。

数据规模与约定

对于 $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}$。

3 4 2
1 1 1
1 2 4
2 2 3
3 3 1

6