골드 러시
면접 대비시간 제한2초메모리 제한512 MB
c 오슐루브와 n일간의 금 가격이 주어질 때, 매일 금을 사고팔 수 있고 마지막 날 금을 모두 현금으로 바꾼다고 할 때 n일째 끝에 얻을 수 있는 최대 오슐루브를 구한다.
문제
네버랜드는 지난 몇 달 동안 다시 매우 심각한 경제 위기를 겪었다. 네버랜드의 화폐인 오슬루브의 금 1단위에 대한 가치는 매우 빠르게 변한다. 자신의 저축을 걱정하는 네버랜드 사람들은 저축을 금화로 바꾸려 한다.
데이터 과학자인 닥터 프레딕트맨은 지난 40년간의 데이터를 바탕으로 앞으로 n일 동안 금화 한 닢의 가격(오슬루브)을 예측했다. 그는 자신의 예측을 믿으며, 그 예측을 바탕으로 저축을 늘리려 한다. 첫째 날 시작 시점에 c 오슬루브를 가지고 있다고 가정할 때 n번째 날이 끝났을 때 자신의 저축이 얼마인지 궁금해했다. 닥터 프레딕트맨은 프로그래머가 아니므로, 당신에게 답을 구해 달라고 부탁한다.
입력
입력의 첫째 줄에는 두 정수 c (0 ⩽ c ⩽ 3000)와 n (0 ⩽ n ⩽ 30)이 주어진다. c는 닥터 프레딕트맨의 초기 저축(오슬루브)이고, n은 예측 기간이다. 다음 n개의 줄에는 각각 정수 pi (1000 ⩽ pi ⩽ 2000)가 주어지며, 이는 i번째 날(1 ⩽ i ⩽ n)의 금화 한 닢 가격(오슬루브)이다.
출력
닥터 프레딕트맨이 n번째 날이 끝났을 때 남아 있는 모든 금화(있을 경우)를 오슬루브로 교환한다고 가정할 때, n번째 날이 끝났을 때 얻을 수 있는 최대 저축을 정수 하나로 출력한다.