33273번 - $\textbf{multiple}\text{ sequence}$

문제

$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을 대신 출력한다.

제한

힌트