Background

Special for beginners, ^_^

Description

有一只虫子需要从左边第一列爬到右边第一列。每次可以爬到右边、右上或者右下三个格子中的一个，爬行过程中需要经过恰好n个鞍点（比左右的相邻点都高且比上下的相邻点都低且四邻域可达）。虫子有恐高症，所以希望经过的每个格子的总海拔最小。有一些点由于被水淹了，所以不能经过。

Format

Input

第一行给出三个整数r、c和n，分别表示行数、列数（3 ≤ r, c ≤ 500）和必须恰好经过的鞍点数（0 ≤ n ≤ 10）。接下来r行，每行给出c个高度，不能访问的点用-1表示，其他点高度为不超过1000的非负整数。

Output

如果存在可行的路径，则输出路径经过的点的总高度，否则输出"impossible"。

Samples

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

14

Limitation

1s, 1024KiB for each test case.