Multiple sequence

Time limit0.5sMemory limit1024 MB

Summary

Choose N integers from M kinds, each kind limited to c_i copies, so every term is a multiple of the previous one, and find the maximum possible sum.

Level: Medium6 of 10
Topics: Dynamic programming, Math
Solved: No attempts yet

Problem

There are $M$ kinds of positive integers. The $i$ -th integer $x\_i$ has $c\_i$ copies. Choose $N$ of these integers and build a sequence $A$ of length $N$ that satisfies the condition below. Find the maximum possible sum of $A$ .

$A\_{j + 1}$ is a multiple of $A\_j$ . $(1 \le j \lt N)$

Input

The first line contains the length $N$ of sequence $A$ and the number of kinds $M$ , separated by a space. $(1 \le N, M \le 500)$ From the second line onward, each of the next $M$ lines gives one integer's information. The $i$ -th line contains a positive integer $x\_i$ and $c\_i$ , separated by a space. All $x\_i$ are distinct. $(1 \le x\_i, c\_i \le 10^9)$

Output

Print the maximum sum of sequence $A$ . If no such sequence $A$ exists, print -1.

Examples3

Example 1
Input
```
4 5
12 1
8 2
1 4
6 3
2 4
```
Expected output
```
30
```
Example 2
Input
```
3 3
81 81
9 9
3 3
```
Expected output
```
243
```
Example 3
Input
```
9 5
2 1
3 6
5 3
7 8
11 3
```
Expected output
```
-1
```