Bajteksの父親はたくさんのパンケーキを焼きました。彼はそれらを $n$ 個の山に積み上げ、各山には $m$ 枚のパンケーキがあります。各山のパンケーキは大きい順に積まれています（つまり、一番大きいパンケーキが山の一番下にあります）。Bajteksはこれらのパンケーキのうち $k$ 枚を食べることが許されました。キッチンが散らかるのを防ぐため、Bajteksは山の一番上にあるパンケーキしか食べることができません（一番下にある大きなパンケーキを抜き取ろうとすると、パンケーキがキッチン中に散らばってしまうことを父親が心配しているためです）。

Bajteksはすぐに、このルールが自分にとって不利であることに気づきました。結局のところ、一番大きなパンケーキは山の一番下にあるからです。そこで彼は、いくつかの山をひっくり返しました。彼はすべての山をひっくり返したかったのですが、時間が足りず、今では父親が彼のあらゆる動きを注意深く監視しています。そのため、Bajteksはできるだけ大きな合計サイズのパンケーキを食べられるように計画を立てなければなりません。

入力

入力の最初の行には、3つの整数 $n, m, k$ ($n, m \ge 1; n \cdot m \le 300\,000; 1 \le k \le n \cdot m$) が含まれており、それぞれパンケーキの山の数、各山にあるパンケーキの数、Bajteksが食べることのできるパンケーキの数を表します。

続く $n$ 行には、各山の説明が記載されています。$i$ 番目の行には、$m$ 個の整数 $a_{i,1}, \dots, a_{i,m}$ ($1 \le a_{i,j} \le 10^{12}$) が含まれています。数 $a_{i,j}$ は、$i$ 番目の山の上から $j$ 番目のパンケーキのサイズを表します。各 $i$ について、$a_{i,j} \ge a_{i,j+1}$ がすべての $j$ で成り立つか、あるいは $a_{i,j} \le a_{i,j+1}$ がすべての $j$ で成り立ちます。

出力

Bajteksが食べることのできる $k$ 枚のパンケーキの合計サイズの最大値を1つの整数で出力してください。

入出力例

入力 1

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

出力 1

11

入力 2

2 3 5
999999999999 1000000000000 1000000000000
1000000000000 1000000000000 999999999999

出力 2

4999999999999

注記

最初の例では、合計サイズ11のパンケーキを食べるために、例えば最初の山から3枚すべて（サイズ1, 2, 3の順）、そして最後の山から上の2枚（サイズ3, 2の順）を食べることができます。Bajteksが合計サイズ11を超えるパンケーキを食べることはできないことが証明できます。

2番目の例では、Bajteksは1枚を除いてすべてのパンケーキを食べることができます。2番目の山の一番下のパンケーキを残すのが最も得策です。