소들은 타고난 신중함에도 주택 담보 시장에서 손해를 보고 주식을 시도합니다. 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을 사야 합니다. 둘째 날 팔고 즉시 주식 2를 사면 은행에 4와 주식 2 한 주가 있습니다. 마지막 날 20에 팔아 은행 돈과 총 24입니다.

입력

• 1행: 공백 구분 정수 $S$, $D$, $M$.
• $2,\ldots,S+1$행: $s+1$행에 주식 $s$의 $1,\ldots,D$일 가격 $D$개 $PR_{sd}$.

출력

• 1행: $D$일 매도 후 최대 돈.

예제

입력 1

2 3 10
10 15 15
13 11 20

출력 1

24

문제 제작: Rob Kolstad(?), 2008