주식 시장

Evelina는 부자가 되기 위해 주식 시장에서 투기를 시작하려 한다. 사실 그녀는 경제에 별로 관심이 없으며 신문에서 첫 번째 주가보다 더 읽으려고 하지 않는다. 하지만 그녀는 다른 모든 사람이 일을 복잡하게 만들고 있을 뿐이라고 생각한다. 적절한 때에 주식을 사고팔면, 우리가 $A$라고 부르는 이 회사 하나만으로도 충분히 돈을 벌 수 있다. 친구들에게 그들이 먹는 피시볼의 양을 항상 물어본 덕분에, 그녀는 앞으로 $N$일 동안의 $A$ 주가를 정확히 예측하는 법을 익혔다. 그녀가 $100$ SEK을 가지고 시작하여 최적으로 투자할 때, 그 기간이 끝날 때 보유하게 되는 금액을 계산하는 프로그램을 작성하라. 그녀는 절대로 돈을 빌릴 수 없으며, 자신의 돈을 사용해야 한다.

주가는 매일 갱신되며 주식을 매수할 때와 매도할 때 동일하다. Evelina는 매일 원하는 양의 주식을 사거나, 원하는 양의 주식을 팔거나, 아무것도 하지 않을 수 있다. 그녀가 매수하는 양은 정수일 필요가 없다. 각 거래마다 고정 중개 수수료를 내야 한다. 수수료는 현금으로 지불한다. 즉, 주식을 사기 전에 수수료를 내야 하고, 주식을 판 뒤에도 수수료를 내야 한다.

채점

제출한 해법은 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ | $30$ | $N \le 14$

$2$ | $40$ | $N \le 1\,000$

$3$ | $30$ | 추가 제한 없음.

첫 번째 줄에는 일수를 나타내는 정수 $N$ ($2 \le N \le 100\,000$)이 주어진다.

두 번째 줄에는 거래당 수수료를 SEK 단위로 나타내는 소수 $Q$ ($0 \le Q \le 100$)가 주어진다.

그다음에는 $N$개의 줄이 주어지며, 각 줄에는 각 날짜의 주가를 나타내는 소수가 하나씩 주어진다. 가격은 항상 $1$에서 $1\,000$ SEK 사이이다.

모든 소수는 소수점 아래 자릿수가 최대 $10$개이다.

$N$일 후 그녀가 보유할 수 있는 최대 금액을 출력한다. 답의 상대 오차 또는 절대 오차가 최대 $10^{-5}$이면 정답으로 인정된다.