Папа Байтека напек много блинов. Он сложил их в $n$ стопок по $m$ блинов в каждой. Блины в каждой стопке сложены от самого большого к самому маленькому (то есть самый большой блин находится внизу стопки). Он разрешил Байтеку съесть $k$ из этих блинов. Чтобы избежать беспорядка на кухне, Байтеку разрешается есть только блины с верхушки стопки (он не может вытаскивать самые большие блины снизу, так как папа опасается, что это приведет к тому, что блины будут разбросаны по всей кухне).

Байтеку быстро стало понятно, что эти правила ему не на руку — в конце концов, самые большие блины находятся внизу стопок — и он успел перевернуть некоторые стопки вверх дном. Он хотел перевернуть все, но не успел, а теперь папа внимательно следит за каждым его движением. Поэтому Байтеку нужно спланировать, как съесть как можно больше блинов.

Входные данные

В первой строке входных данных содержатся три целых числа $n$, $m$ и $k$ ($n, m \ge 1$; $n \cdot m \le 300\,000$; $1 \le k \le n \cdot m$), обозначающие количество стопок блинов, количество блинов в каждой стопке и количество блинов, которые Байтеку разрешено съесть.

В следующих $n$ строках содержатся описания стопок; в $i$-й из этих строк находится последовательность из $m$ целых чисел $a_{i,1}, \dots, a_{i,m}$ ($1 \le a_{i,j} \le 10^{12}$). Число $a_{i,j}$ обозначает размер $j$-го блина сверху в $i$-й стопке. Для каждого $i$ выполняется условие $a_{i,j} \ge a_{i,j+1}$ для всех $j$ или $a_{i,j} \le a_{i,j+1}$ для всех $j$.

Выходные данные

Выведите одно целое число — максимально возможный суммарный размер $k$ блинов, которые может съесть Байтек.

Примеры

Пример 1

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

11

Пример 2

2 3 5
999999999999 1000000000000 1000000000000
1000000000000 1000000000000 999999999999

4999999999999

Примечание

В первом примере, чтобы съесть блины с суммарным размером 11, Байтеку достаточно, например, съесть все три блина из первой стопки (размерами 1, 2 и 3 соответственно), а также два верхних блина из последней стопки (размерами 3 и 2 соответственно). Можно доказать, что Байтек не может съесть блины с суммарным размером больше 11.

Во втором примере Байтек может съесть все блины, кроме одного. Ему выгодно оставить несъеденным нижний блин из второй стопки.