시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 188 44 21 25.926%

문제

동호는 주식으로 떼돈을 벌려고 한다.  동호가 주식왕이라 불리는 이유는 미래의 주식 값의 변화까지도 정확히 예측하기 때문이다. 현재 동호는 C개의 주식을 눈여겨보고 있고 이 주식들을 일정한 기간동안 적당히 사고팔면서 돈을 부풀릴 계획이다.

Day 1

Day 2

Day 3

주식 1

10

15

15

주식 2

13

11

20

위와 같이 각 주식에 대해 날짜에 따른 주식 비용이다. 처음 동호가 가지고 있는 자본이 10이라 할 때 3일동안 동호가 최대로 돈을 벌 수 있는 방법은 첫째 날 주식 1을 매입한다. 둘째 날 주식 1을 매각하고 주식 2를 매입한다. 셋째 날 주식 2를 매각하면 초기 자본을 포함하여 총 24의 돈을 갖게 된다.

문제는 주식 종류와 기간, 초기 자금 등이 주어졌을 때 동호가 최종적으로 가질 수 있는 돈의 최대값을 구하는 것이다.

입력

첫 줄에는 주식의 개수 N(1 ≤ N ≤ 50)과 주식 매입 및 매각을 할 기간 D(2 ≤ D ≤ 10), 초기 자금 M(1 ≤ M ≤ 200,000)이 공백으로 구분되어 주어진다. 두 번째 줄부터 S+1번째 줄까지 각 줄에는 각각 주식이 날짜에 따라 변하는 값이 입력된다.

출력

첫 줄에 동호가 최종적으로 가질 수 있는 돈의 최댓값을 출력한다. 출력값이 500,000을 넘지 않는 데이터만 주어진다.

예제 입력

2 3 10
10 15 15
13 11 20

예제 출력

24

힌트