문제
$M$가지 종류의 양의 정수가 주어진다. 그중 $i$번째 정수 $x_i$는 $c_i$개 있다. 이 정수들 중 $N$개를 선택하여 다음 조건을 만족하도록 만들 수 있는 길이가 $N$인 수열 $A$의 합의 최댓값을 구하여라.
- $A_{j + 1}$는 $A_j$의 배수이다. $(1 \le j \lt N)$
입력
첫째 줄에 수열 $A$의 길이 $N$, 양의 정수의 종류 $M$이 공백으로 구분되어 주어진다. $(1 \le N, M \le 500)$
둘째 줄부터 $M$개의 줄에 걸쳐 각 정수의 정보가 주어진다. 그중 $i$번째 줄은 양의 정수 $x_i$, $c_i$가 공백으로 구분되어 주어진다. 주어지는 모든 $x_i$는 서로 다르다. $(1 \le x_i, c_i \le 10^9)$
출력
수열 $A$의 합의 최댓값을 출력한다. 만약 수열 $A$가 존재하지 않는다면 -1을 대신 출력한다.
예제 입력 1
4 5 12 1 8 2 1 4 6 3 2 4
예제 출력 1
30
$A = [ 6, 6, 6, 12 ]$
예제 입력 2
3 3 81 81 9 9 3 3
예제 출력 2
243
$A = [ 81, 81, 81 ]$
예제 입력 3
9 5 2 1 3 6 5 3 7 8 11 3
예제 출력 3
-1
출처
Contest > BOJ User Contest > 월간 향유회 > 월간 향유회 2025. 01. B번
- 문제를 만든 사람: wapas
- 문제를 검수한 사람: chogahui05, cologne, jthis, jyheo98, lky7674, utilforever