E. El Gift from Ronaldo
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

We all know that The Pachorverse has infinite timelines; but this problem takes us to the Mr-137 universe, not C-137. In this competitive programming universe, there are many characters that contribute to the main story, including the legendary teams Spokies and QuePerdio.

Our old friend Steven, from the Mr-137 universe, will give us some advice to navigate this chaotic universe. Remember: it doesn't matter where you start learning, as long as you are consistent, you will eventually find an optimal training strategy in competitive programming.

Steven, being self-taught, reads random tutorials from Codeforces. It takes him between one and two months to learn advanced techniques. Over the years, he understood that there are problems that, no matter how hard you try, will force you to give up and explore other areas. Eventually, you will accumulate enough knowledge to face them again. For Steven, learning without the help of others was difficult; that's why he values his mentors who dedicated their time in those days (*).

Steven invites you to solve difficult problems with a rating of +2500 weekly, because the only way to grow is to step out of your comfort zone; it won't be easy, but it won't be impossible either. Time management is crucial; with these problems, one can lose a lot of time without realizing it, so it is advisable to set limits and keep learning.

Steven Ronaldo Tercero has left us another intriguing gift for the competition. This time, your task is to analyze integers under specific conditions related to divisibility.

Given an integer $$$S$$$, an integer $$$N$$$, and a set of $$$K$$$ numbers $$$\{a_1, a_2, \dots, a_K\}$$$, you must count how many numbers less than or equal to $$$N$$$ are divisible by $$$S$$$, but not divisible by any of the numbers in the given set.

Input

The input consists of the following lines:

  • One line contains three integers $$$S$$$, $$$N$$$, and $$$K$$$, where $$$2 \leq S \leq 50$$$, $$$1 \leq N \leq 10^9$$$, and $$$0 \leq K \leq 20$$$.
  • One line contains $$$K$$$ integers $$$a_1, a_2, \dots, a_K$$$ ($$$2 \leq a_i \leq 50$$$) representing the set of restrictions.
Output

Print a single integer: the count of numbers less than or equal to $$$N$$$ that meet the described conditions.

Example
Input
3 10 2
2 5
Output
2
Note

In the given example:

  • The numbers less than or equal to $$$10$$$ that are divisible by $$$3$$$ are $$$3, 6, 9$$$.
  • Of these, $$$6$$$ is divisible by $$$2$$$. Only $$$3$$$ and $$$9$$$ remain, so the answer is $$$2$$$.
(*)Special thanks to Leticia, Vladimir, Rodrigo Castillo, Rolando, Addis, Gauss, Carlos, Miguel Angel, Miguel Iturri, Javier, Diego A., Diego Gabriel, Joaquin Morales, and Tomasz Idziaszek.