Mały C gra w grę polegającą na ustawianiu wojsk. W grze znajduje się $n$ zamków, a każda runda polega na rywalizacji dwóch graczy o te zamki. Każdy gracz dysponuje $m$ żołnierzami i może wysłać $a_i$ żołnierzy do $i$-tego zamku, tak aby łączna liczba żołnierzy nie przekroczyła $m$.
Jeśli gracz wyśle do $i$-tego zamku liczbę żołnierzy ściśle większą niż dwukrotność liczby żołnierzy wysłanych przez przeciwnika, gracz ten przejmuje zamek i zdobywa $i$ punktów.
Mały C ma wkrótce stoczyć pojedynki z $s$ innymi graczami. Strategia rozmieszczenia żołnierzy musi być taka sama we wszystkich $s$ pojedynkach. Mały C poznał strategie, których użyją pozostali gracze, i chce wiedzieć, jaką strategię powinien przyjąć, aby zmaksymalizować swój łączny wynik.
Ponieważ odpowiedź może nie być jednoznaczna, wystarczy wypisać maksymalną możliwą sumę punktów małego C.
Wejście
Pierwsza linia wejścia zawiera trzy dodatnie liczby całkowite $s, n, m$, oznaczające odpowiednio liczbę przeciwników, liczbę zamków oraz liczbę żołnierzy posiadanych przez każdego gracza.
Następnie podano $s$ linii, z których każda zawiera $n$ nieujemnych liczb całkowitych reprezentujących strategię jednego z graczy, gdzie $i$-ta liczba $a_i$ oznacza liczbę żołnierzy wysłanych przez tego gracza do $i$-tego zamku.
Wyjście
Wypisz w jednej linii nieujemną liczbę całkowitą oznaczającą maksymalny wynik, jaki może uzyskać mały C.
Przykład
Przykład 1
1 3 10 2 2 6
Wyjście 1
3
Uwagi 1
Najlepszą strategią małego C jest wysłanie po $5$ żołnierzy do $1$. i $2$. zamku.
Przykład 2
2 3 10 2 2 6 0 0 0
Wyjście 2
8
Uwagi 2
Jedną z najlepszych strategii małego C jest wysłanie $2$ żołnierzy do $1$. zamku, $5$ żołnierzy do $2$. zamku oraz $1$ żołnierza do $3$. zamku.
Podzadania
Dla $10\%$ danych wejściowych: $s=1, n \le 3, m \le 10$.
Dla $20\%$ danych wejściowych: $s=1, n \le 10, m \le 100$.
Dla $40\%$ danych wejściowych: $n \le 10, m \le 100$.
Dla kolejnych $20\%$ danych wejściowych: $s=1$.
Dla $100\%$ danych wejściowych:
- $1 \le s \le 100$
- $1 \le n \le 100$
- $1 \le m \le 2\times 10^4$
- Dla każdego gracza: $a_i \ge 0, \sum\limits_{i=1}^n a_i \le m$.