카드 구매하기

요즘 민규네 동네에서는 PS카드를 모으는 것이 유행이다.

PS카드는 PS(Problem Solving) 분야에서 유명한 사람의 아이디와 얼굴이 적혀 있는 카드다. 카드마다 등급을 나타내는 색이 칠해져 있고, 색은 다음 8가지다.

• 전설카드
• 레드카드
• 오렌지카드
• 퍼플카드
• 블루카드
• 청록카드
• 그린카드
• 그레이카드

카드는 카드팩 단위로만 살 수 있다. 카드팩은 카드가 1개 든 팩, 2개 든 팩, 이런 식으로 카드가 $N$개 든 팩까지 모두 $N$가지다. 카드가 $i$개 든 카드팩의 가격은 $P_i$원이다. 같은 종류의 카드팩을 여러 번 살 수 있다.

민규는 카드 개수가 적은 팩이라도 가격이 비싸면 높은 등급의 카드가 많이 들어 있다는 미신을 믿는다. 그래서 돈을 최대한 많이 내고 카드 $N$개를 사려고 한다.

예를 들어 카드팩이 4가지이고 $P_1 = 1$, $P_2 = 5$, $P_3 = 6$, $P_4 = 7$이면 민규가 카드 4개를 갖는 데 내는 금액의 최댓값은 10원이다. 카드가 2개 든 팩을 두 번 사면 된다.

$P_1 = 5$, $P_2 = 2$, $P_3 = 8$, $P_4 = 10$이면 카드가 1개 든 팩을 네 번 사서 20원을 내는 것이 최댓값이다.

$P_1 = 3$, $P_2 = 5$, $P_3 = 15$, $P_4 = 16$이면 카드가 3개 든 팩과 1개 든 팩을 사서 18원을 내는 것이 최댓값이다.

카드팩 가격이 주어졌을 때, 카드 $N$개를 사려고 민규가 내는 금액의 최댓값을 구하는 프로그램을 작성하시오. $N$개보다 많이 산 다음 남는 카드를 버려서 $N$개를 맞추는 것은 불가능하다. 즉, 산 카드팩에 든 카드 개수의 합은 $N$과 같아야 한다.

첫째 줄에 민규가 사려는 카드의 개수 $N$이 주어진다. ($1 \le N \le 1000$)

둘째 줄에 $P_1$부터 $P_N$까지 순서대로 주어진다. ($1 \le P_i \le 10000$)

첫째 줄에 민규가 카드 $N$개를 갖는 데 내는 금액의 최댓값을 출력한다.