배수 수열

시간 제한0.5초메모리 제한1024 MB

요약

각 항이 앞 항의 배수가 되도록 정수 N개를 고를 때, 각 정수의 사용 가능 개수 안에서 합의 최댓값을 구합니다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 수학
정답자: 아직 제출이 없습니다

문제

$M$ 가지 종류의 양의 정수가 주어진다. 그중 $i$ 번째 정수 $x\_i$ 는 $c\_i$ 개 있다. 이 정수들 중 $N$ 개를 골라 다음 조건을 만족하는 길이 $N$ 의 수열 $A$ 를 만들 때, 수열 $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을 출력한다.

예제3

예제 1
입력
```
4 5
12 1
8 2
1 4
6 3
2 4
```
예상 출력
```
30
```
예제 2
입력
```
3 3
81 81
9 9
3 3
```
예상 출력
```
243
```
예제 3
입력
```
9 5
2 1
3 6
5 3
7 8
11 3
```
예상 출력
```
-1
```