You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时间限制：$1s$

空间限制：$512MB$

题目背景

不好！$piggy$由于沉沦于《三角洲行动》被流放到了时间迷宫执行时间旅行任务！

题目描述

时间迷宫可以看成一个$n*m$的网格，入口在$(1,1)$，即左上角；出口在$(n,m)$，即右下角。而$piggy$被流放到了时间迷宫的入口，$piggy$需要从出口走出去，同时以时间旅行者的身份执行时间旅行任务！

时间旅行任务

规则：

a.初始时刻，时间代价为0

b.时间旅行者只被允许向右/向下走，每走一格，会花费$1$的时间代价。

d.时间旅行者路过网格$(x,y)$时，会受到时间眷顾，从而获得眷顾值。$（眷顾值 = 当前时间代价*时间值）$

e.时间旅行者最多可以使用$t$次时间魔法，时间会暂停，即花费$1$的时间代价，停在原地不动。

f.网格的眷顾值不可被重复获得,且不能在同一个网格使用$2$次以上的时间魔法。

g.在走到网格$(n,m)$时，任务终止，你需要保证你的眷顾值最大化

众所周知，$piggy$是一只绝世大懒猪，他不想自己去计算最大眷顾值是多少，你能帮帮他吗？

输入格式

第一行，三个整数，$t$,$n$和$m$，表示时间魔法次数，网格大小

接下来$n$行，每行$m$个整数，表示时间值$a_{x,y}$

输出格式

共一个整数，表示最大眷顾值

样例输入

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

样例输出

52

数据范围