시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB276726527.897%

문제

드디어 타임머신을 만들어낸 욕심쟁이 과학자 숭고한은 타임머신을 타고 과거로 돌아가 큰돈을 벌고 싶다. 하지만 기술의 한계로 $N$일 동안만 과거에 머무를 수 있다. 

평소 SKH 기업에 관심이 많았던 숭고한은 과거에 머무른 기간 동안의 SKH 기업의 주가를 전부 알고 있다.

숭고한은 성격이 급하기 때문에 영끌 대출 후 풀매수, 풀매도만을 이용해 투자를 하려고 한다.

즉, 주식을 매수(구매)할 때는 현재 갖고 있는 돈의 정확히 $K$배를 대출받아 주식을 최대한 많이 매수하고, 주식을 매도(판매)할 때는 가지고 있는 주식을 전량 매도해야 한다.

또한, 다음과 같은 규칙들을 지켜야 한다.

  • 주식을 쪼개서 매수할 수 없다. 
  • 주식을 매수하지 않는다면 대출받을 수 없다.
  • 대출금이 있을 경우 모두 상환하기 전까지 대출받을 수 없다.
  • 주식을 매도해서 번 돈은 매도하는 즉시 들어온다.
  • 주식을 매수하면 다음 날부터 매도할 수 있다. (매도한 당일 매수는 가능)
  • 돌아올 때는 대출금을 갚지 않고 돌아와도 무방하다.
  • 돌아올 때 주식은 전부 매도한 상태로 돌아와야 한다.

현재로 돌아올 때 가지고 돌아올 수 있는 돈의 최댓값은 얼마인가?

입력

첫째 줄에 과거에 머무를 수 있는 기간 $N(2\le N \le 10)$, 숭고한이 가지고 간 돈 $M(0 \le M \le 1\,000)$, 대출할 수 있는 한도 $K(1 \le K \le 4)$가 공백으로 구분되어 주어진다.

둘째 줄에 과거로 돌아간 시점부터 $i$번째 날의 주가 $p_i$가 주어진다. ($1 \leq i \leq N, 100 \le p_i \le 1\,000, p_i$는 정수)

출력

과거에서 현재로 돌아올 때 가지고 돌아올 수 있는 돈의 액수의 최댓값을 출력한다.

돌아올 때 대출금은 갚을 필요가 없다는 점에 유의하자.

예제 입력 1

8 1000 2
300 200 400 500 800 100 1000 200

예제 출력 1

588000

다음과 같이 행동하면 최대 금액을 얻을 수 있다.

  • 2일차: 3000원(대출금 2000원 포함)으로 15개 매수
  • 3일차: 15개 매도(잔액 6000원) 후 2000원 상환(잔액 4000원), 12000원(대출금 8000원 포함)으로 30개 매수
  • 4일차: 30개 매도(잔액 15000원) 후 8000원 상환(잔액 7000원), 21000원(대출금 14000원 포함)으로 42개 매수
  • 5일차: 42개 매도(잔액 33600원) 후 14000원 상환(잔액 19600원)
  • 6일차: 58800원(대출금 39200원 포함)으로 588개 매수
  • 7일차: 588개 매도 후 잔액 588000원을 갖고 귀환

예제 입력 2

3 100 2
400 500 700

예제 출력 2

100

대출을 받아도 주식을 매수할 수 없으므로, 갖고 돌아올 수 있는 금액은 처음에 갖고 있던 100원이다.