Bajtek 的爸爸煎了許多鬆餅，並將它們堆疊成 $n$ 堆，每堆各有 $m$ 個鬆餅。每一堆鬆餅原本都是由大到小排列（即最大的鬆餅在最底部）。爸爸允許 Bajtek 吃掉其中的 $k$ 個鬆餅。為了避免廚房變得一團亂，Bajtek 只能從鬆餅堆的頂部開始吃（他不能從底部抽出最大的鬆餅，因為爸爸擔心這樣會導致鬆餅散落滿地）。

Bajtek 很快就發現這些規則對他不利——畢竟最大的鬆餅都在堆疊的底部——於是他在爸爸沒注意時，將其中一些鬆餅堆上下顛倒了。他原本想把所有的鬆餅堆都顛倒過來，但還沒來得及做完，爸爸就開始警覺地盯著他的一舉一動。因此，Bajtek 必須規劃如何吃掉總大小最大的 $k$ 個鬆餅。

輸入格式

第一行包含三個整數 $n, m$ 和 $k$ ($n, m \ge 1; n \cdot m \le 300\,000; 1 \le k \le n \cdot m$)，分別代表鬆餅堆的數量、每堆鬆餅的數量，以及 Bajtek 可以吃掉的鬆餅數量。

接下來的 $n$ 行描述各個鬆餅堆；第 $i$ 行包含 $m$ 個整數 $a_{i,1}, \dots, a_{i,m}$ ($1 \le a_{i,j} \le 10^{12}$)。數字 $a_{i,j}$ 代表第 $i$ 堆中由上往下數第 $j$ 個鬆餅的大小。對於每一堆 $i$，滿足對於所有的 $j$，要麼 $a_{i,j} \ge a_{i,j+1}$，要麼 $a_{i,j} \le a_{i,j+1}$。

輸出格式

輸出一個整數——Bajtek 可以吃掉的 $k$ 個鬆餅的最大總大小。

範例

輸入格式 1

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

輸出格式 1

11

說明

在第一個範例中，為了吃到總大小為 11 的鬆餅，Bajtek 可以選擇吃掉第一堆的所有三個鬆餅（大小分別為 1, 2, 3），以及最後一堆最上面的兩個鬆餅（大小分別為 3, 2）。可以證明 Bajtek 無法吃到總大小超過 11 的鬆餅。

輸入格式 2

2 3 5
999999999999 1000000000000 1000000000000
1000000000000 1000000000000 999999999999

輸出格式 2

4999999999999

說明

在第二個範例中，Bajtek 可以吃掉除了其中一個以外的所有鬆餅。他最划算的選擇是留下第二堆最底部的那個鬆餅不吃。