24885번 - 주식

문제

드디어 타임머신을 만들어낸 욕심쟁이 과학자 숭고한은 타임머신을 타고 과거로 돌아가 큰돈을 벌고 싶다. 하지만 기술의 한계로 $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$는 정수)

출력

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

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

제한

힌트