Маленький C играет в игру по расстановке войск. В игре есть $n$ замков, и в каждом раунде два игрока сражаются за эти замки. У каждого игрока есть $m$ солдат, которых можно распределить по замкам: на $i$-й замок можно отправить $a_i$ солдат так, чтобы общее количество солдат не превышало $m$.

Если игрок отправляет на $i$-й замок количество солдат, строго превышающее удвоенное количество солдат противника на этом же замке, то этот игрок захватывает замок и получает $i$ очков.

Маленькому C предстоит сразиться с $s$ другими игроками. Для всех $s$ поединков он должен использовать одну и ту же стратегию распределения солдат. Маленький C узнал стратегии, которые собираются использовать остальные $s$ игроков, и хочет определить стратегию, которая максимизирует его суммарный счет.

Так как ответ может быть не единственным, вам нужно вывести только максимально возможный суммарный счет маленького C.

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

Первая строка содержит три целых положительных числа $s, n, m$, обозначающие количество противников, количество замков и количество солдат у каждого игрока соответственно.

Далее следуют $s$ строк, каждая из которых содержит $n$ неотрицательных целых чисел, описывающих стратегию одного игрока, где $i$-е число $a_i$ — это количество солдат, отправленных этим игроком на $i$-й замок.

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

Выведите одно неотрицательное целое число — максимальный суммарный счет, который может получить маленький C.

Примеры

Пример 1

1 3 10
2 2 6

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

3

Примечание 1

Оптимальная стратегия маленького C — отправить по $5$ солдат на $1$-й и $2$-й замки.

Пример 2

2 3 10
2 2 6
0 0 0

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

8

Примечание 2

Одна из оптимальных стратегий маленького C — отправить $2$ солдата на $1$-й замок, $5$ солдат на $2$-й замок и $1$ солдата на $3$-й замок.

Подзадачи

Для $10\%$ данных гарантируется $s=1, n \le 3, m \le 10$.

Для $20\%$ данных гарантируется $s=1, n \le 10, m \le 100$.

Для $40\%$ данных гарантируется $n \le 10, m \le 100$.

Для еще $20\%$ данных гарантируется $s=1$.

Для $100\%$ данных гарантируется:

• $1 \le s \le 100$
• $1 \le n \le 100$
• $1 \le m \le 2\times 10^4$
• Для каждого игрока $a_i \ge 0, \sum\limits_{i=1}^n a_i \le m$.