시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 276 | 72 | 65 | 27.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$는 정수)
과거에서 현재로 돌아올 때 가지고 돌아올 수 있는 돈의 액수의 최댓값을 출력한다.
돌아올 때 대출금은 갚을 필요가 없다는 점에 유의하자.
8 1000 2 300 200 400 500 800 100 1000 200
588000
다음과 같이 행동하면 최대 금액을 얻을 수 있다.
3 100 2 400 500 700
100
대출을 받아도 주식을 매수할 수 없으므로, 갖고 돌아올 수 있는 금액은 처음에 갖고 있던 100원이다.