Несмотря на врождённую осторожность, коровы пострадали на ипотечном рынке и пробуют акции. Bessie предвидит цены: не только сегодняшние для $S$ $(2 \le S \le 50)$ акций, но и будущие всего на $D$ дней $(2 \le D \le 10)$.

Даны матрица текущих и будущих цен по дням $(1 \le PR_{sd} \le 1,000)$ и начальные $M$ $(1 \le M \le 200,000)$ денег. Найдите оптимальные покупки и продажи для максимальной выгоды при продаже в последний день. Покупают целое число акций, тратить все или вообще хоть что-то не обязательно. Прибыль не превысит 500,000.

Пример растущего бычьего рынка, любимого Bessie: $S=2$, $D=3$, для инвестиций 10. Столбцы — цена сегодня, завтра, послезавтра.

                   Today's price
                   |   Tomorrow's price
                   |   |  Two days hence
             Stock |   |  | 
              1    10 15 15
              2    13 11 20

Для прибыли в день 1 покупают акцию 1. В день 2 продают и сразу покупают акцию 2: в банке 4 и одна акция 2. В последний день продажа приносит 20, вместе с банком 24.

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

• Строка 1: целые $S$, $D$, $M$ через пробел.
• Строки $2,\ldots,S+1$: строка $s+1$ содержит $D$ цен $PR_{sd}$ акции $s$ на дни $1,\ldots,D$.

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

• Строка 1: максимум денег после продажи в день $D$.

Примеры

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

2 3 10
10 15 15
13 11 20

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

24

Автор: Rob Kolstad(?), 2008