Sum of Numbers with Specific Prime Factors

Given a natural number \( m \) and a set \( P \) of primes, compute the sum of all natural numbers \( x \) (where \( 1 \le x \le m \)) such that the set of prime factors of \( x \) has a non-empty intersection with \( P \). Note that \( 1 \) is not considered since it has no prime factors.

Problem Analysis:

• You are given two integers \( m \) and \( n \), where \( m \) is the upper bound and \( n \) is the number of primes in the set \( P \).
• The next input line contains \( n \) space-separated prime numbers.
• Your task is to sum all numbers \( x \) such that \( 1 \le x \le m \) and at least one of \( x \)'s prime factors is in \( P \).

Hint: Instead of factorizing each number, you can mark multiples of each prime in \( P \) and accumulate the sum without duplication.

inputFormat

The first line contains two integers \( m \) and \( n \) (\( 1 \le m, n \le 10^6 \) for instance), where \( m \) is the maximum number and \( n \) is the count of primes in the set \( P \).

The second line contains \( n \) space-separated prime numbers.

outputFormat

Output a single integer representing the sum of all natural numbers \( x \) (\( 1 \le x \le m \)) that have at least one prime factor from the given set \( P \).

sample

10 2
2 3

42