투자 마스터

면접 대비

시간 제한2초메모리 제한512 MB

요약

d일 동안 n개 주식의 가격이 주어질 때, 수수료 없이 매매해 마지막 날 현금을 최대로 만드는 방법을 구한다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 그리디, 구현, 수학
정답자: 아직 제출이 없습니다

문제

오랜 연구 끝에 이쿠타 군은 미래 예지 능력을 손에 넣었다! 그가 이 연구에 쏟아부은 시간과 돈은 막대했지만, 마침내 보답받을 때가 온 것이다. 우선 돈을 되찾기 위해 이쿠타 군은 주식 투자를 시작하기로 했다.

이쿠타 군은 현재 주식을 전혀 보유하고 있지 않으며, $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$ 이하가 됨이 보장된다.

예제4

예제 1
입력
```
2 2 5
3 2
5 4
```
예상 출력
```
9
```
예제 2
입력
```
1 2 5
6
10000
```
예상 출력
```
5
```
예제 3
입력
```
2 3 5
4 5
6 3
8 5
```
예상 출력
```
11
```
예제 4
입력
```
3 3 10
10 9 6
8 7 3
7 5 1
```
예상 출력
```
10
```