Justin 和 Fred 正在进行一次公路旅行，从西向东横穿他们的州。他们有几条公路旅行规则：

1. 他们必须玩得开心！
2. 旅行必须从该州西侧边缘的某处开始，并在东侧边缘的某处结束。
3. 旅行中的每一步都必须直接向东、向东北斜向或向东南斜向移动。
4. 他们希望恰好经过 $n$ 个“山口”（定义见下文）。
5. 由于 Fred 对高海拔比较敏感，他们希望最小化旅行过程中海拔高度的累积总和。
6. 他们必须玩得开心！

由于 Justin 和 Fred 是向东旅行的，“山口”是指这样一个位置：其东侧和西侧的海拔高度严格较低，且其北侧和南侧的海拔高度严格较高。考虑图 E.1 所示的海拔地图。不可行驶的位置（由于水域或坚持留在州内）以黑色显示，而山口以灰色显示。与边界或不可行驶位置相邻的位置不能被视为山口。

图 E.1：海拔地图示例

输入格式

输入的第一行包含三个整数 $r, c, n$，分别表示州地形表示的行数和列数（$3 \le r, c \le 500$）以及需要经过的山口的准确数量（$0 \le n \le 10$）。 接下来的 $r$ 行，每行包含 $c$ 个海拔数值。不可行驶的位置用 $-1$ 表示，所有其他海拔高度在 $0$ 到 $1000$ 之间。保证东侧和西侧边界上至少各有一个可行驶的位置。

输出格式

输出满足公路旅行规则的最优路径的海拔高度总和。如果不存在这样的路径，则输出 impossible。

样例

样例输入 1

5 7 2
-1 -1 2 5 4 3 1
3 4 1 4 1 2 1
3 4 5 5 3 4 5
2 3 2 1 2 3 2
-1 5 4 1 4 4 2

样例输出 1

14

样例输入 2

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

样例输出 2

impossible