Sum of Multiples

Interview

Time limit1sMemory limit512 MB

Summary

Given N and a list of divisors K_i, sum every integer from 1 to N that is divisible by at least one K_i, counting each qualifying number once.

Level: Easy3 of 10
Topics: Implementation, Math, Brute force
Solved: No attempts yet

Problem

You are given a positive integer $N$ and $M$ positive integers $K_i$ . Find the sum of all integers between $1$ and $N$ inclusive that are multiples of at least one of the $K_i$ .

Input

The first line contains $N$ and $M$ . ( $2 \le N \le 1000$ , $1 \le M < N$ )

The next line contains $M$ integers $K_i$ . ( $2 \le K_i \le 1000$ )

No two $K_i$ are equal, and they are given in ascending order.

Output

Print the sum of the multiples.

Examples2

Example 1
Input
```
10 2
2 3
```
Expected output
```
42
```
Example 2
Input
```
1000 3
3 5 7
```
Expected output
```
272066
```