大欢喜帝
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

第五代皇帝大欢喜帝即位时，有民众的欢呼与喝彩三日三夜不绝的记载。起先人们认为这是单纯的夸张表现，但后来调查发现这一记载乃是事实。因为最先停止拍手的一百人，都被大欢喜帝当做庆典的活供用PK点燃，烧成黑炭的躯体更成了王宫的装饰……
——《自新世界》

大欢喜帝殿前广场的民众站成 N×M 的方阵，每个人都奋力的鼓掌，直至耗尽体力。但人是有极限的，第i行j列的体力为e_{i,j}，每鼓掌1秒，需要消耗1点体力。当人们看到有人被焚烧时，出于对生的追求，他们会瞬间迸发更多的体力。具体的，剩余体力会增加50\%(向上取整)。

因为每个人都专心鼓掌，所以他们只会关注自己正前方第一个人是否被焚烧。

现在大欢喜帝想要焚烧至少K个民众，请问至少需要多少秒？

注：大欢喜帝会立即焚烧掉所有停止鼓掌的人

输入描述:

输入共N+1行，第一行包括三个整数N,M,K(1\leq N \leq 50,1\leq M \leq 5000 ,0 \leq K \leq N \times M)，分别表示民众阵列的行、列与大欢喜帝想要焚烧的人数下限。

接下来为一个N \times M的矩阵(1 \leq e_{i,j} \leq 10^9)，表示民众初始体力。

若存在存活的两个人A、B 分别在第i行j列和i’行j列，且满足i< i’，则表示A在B的正前方。
同时，若不存在存活的人C在k行j列，i <k< i’，那么A就是B正前方第一个人。

输出描述:

输出1个整数，含义见题目描述。
示例1

输入

复制 
3 1 2
1
1
2

输出

复制 
1
示例2

输入

复制 
3 1 3
1
1
2

输出

复制 
3
示例3

输入

复制 
3 2 5
3 1
2 5
4 3

输出

复制 
6

备注:

第一个样例中：
第1秒后，前两行的人停止鼓掌，被大欢喜帝焚烧，此时，正好满足大欢喜帝焚烧2个人的要求。故只需要1秒。

第二个样例中：
第1秒后，前两行的人停止鼓掌，被大欢喜帝焚烧，此时，第3行的人看到前一个人被焚烧，收到激励，额外获得\lceil 1×50\rceil =1 秒，故总共需要花费3秒。