生来慎重な牛たちも住宅ローン市場で痛手を受け、株を試します。幸い 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 日目に売り、すぐ銘柄 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