카드 구매하기

요즘 민규네 동네에서는 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$ 개를 갖는 데 내는 금액의 최댓값을 출력한다.