22442번 - Invest Master 다국어

長年の研究の末、イクタ君は未来予知能力を手に入れた！　彼がこの研究に費やした時間や金銭は莫大なものであったが、ついに報われる時がやってきたのだ。手始めに金銭を取り戻すため、イクタ君は株式投資を始めることにした。

イクタ君は現在株式は全く保有しておらず、 $x$ 円を所持している。彼が投資対象に定めた株式は $n$ 種類で、それらについて今日から $d$ 日分の株価を予知することに成功した。その結果、驚くべきことに今日から $d$ 日間は日中の株価変動が全くないことが判明した。つまり、今日を1日目としたときの $i $（$1 \leq i \leq d$）日目の株式 $j$ （$1 \leq j \leq n$）の株価 $p_{i,j}$ 円がわかっている。イクタ君はそれぞれの日に自由に株式を売買できる。すなわち、任意の時点で以下の操作（購入・売却）を任意の順番で任意の回数行える。ただし、各操作の前後での所持金と株式の保有単位数は非負整数でなければならない。

• 購入 : $i$ 日目に、株式の種類 $j$ （$1 \leq j \leq n$）を一つ選び、所持金 $p_{i,j}$ 円を支払い1単位の株式 $j$ を得る。

• 売却 : $i$ 日目に、株式の種類 $j$ （$1 \leq j \leq n$）を一つ選び、1単位の株式 $j$ を支払い $p_{i,j}$ 円を得る。

（彼が研究に没頭する間に証券取引システムは大きな発達を遂げ、取引手数料はかからなくなった。）

イクタ君は大学で情報科学を修めていたが、未来予知研究に明け暮れるすえに大学で学んだことをすべて忘れてしまっていた。そんな彼の代わりに最終日の所持金を最大化するプログラムを書いてあげてほしい。

入力は以下の形式で与えられる。

$n$ $d$ $x$

$p_{1,1}$ ... $p_{1,n}$

...

$p_{d,1}$ ... $p_{d,n}$

• $n$ : 株式の種類数

• $d$ : 日数

• $x$ : 1日目の所持金

• $p_{i,j}$ :$ i $日目の銘柄$j$の株価（今日を1日目とする）

最適に投資した場合の最終日の所持金を1行に出力せよ。

入力中の各変数は以下の制約を満たす整数である。

• $1 \leq n \leq 10$

• $1 \leq d \leq 10$

• $1 \leq x, p_{i,j} \leq 10^5$

• 最終日の所持金が $10^5$ 以下となることが保証されている。