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

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

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

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

Input

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

n d x 
p1,1 ... p1,n
...
pd,1 ... pd,n

Constraints

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

Output

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

Sample Input 1

2 2 5
3 2
5 4

Output for the Sample Input 1

9

Sample Input 2

1 2 5
6
10000

Output for the Sample Input 2

5

Sample Input 3

2 3 5
4 5
6 3
8 5

Output for the Sample Input 3

11

Sample Input 4

3 3 10
10 9 6
8 7 3
7 5 1

Output for the Sample Input 4

10