Problem Description

Xiaoming is learning music. He finds that playing different instruments requires matching different beats. Now there are $N$ kinds of instruments, and each instrument has its own “beat period” (in seconds).

In music performance, if a certain moment is exactly an integer multiple of an instrument’s beat period, then this instrument will make a sound at that moment. For example, an instrument with a beat period of $3$ seconds will make a sound at the $3$rd second, the $6$th second, the $9$th second, and so on.

Xiaoming wants to know: within the first $T$ seconds (i.e., from the $1$st second to the $T$th second, including the $T$th second), how many moments are there when exactly $K$ instruments make sounds at the same time?

Input Format

The first line contains three integers $N, T, K$, representing the number of instruments, the observation duration, and the number of instruments that make sounds simultaneously.

The second line contains $N$ integers $p_1, p_2, \dots, p_N$, representing the beat period of each instrument (unit: seconds).

Output Format

Output one line with one integer, representing the number of moments when exactly $K$ instruments make sounds simultaneously.

3 12 2
2 3 4

3

4 20 3
2 3 5 6

3

5 100 1
7 11 13 17 19

36

Hint

Sample Explanation 1

The instrument periods are $2$, $3$, and $4$ seconds. Within the first $12$ seconds, the sounding situation at each moment is shown in the table below:

In the table, “✓” means the instrument makes a sound at that moment, and “-” means it does not.

The moments when exactly $2$ instruments make sounds simultaneously are $t = 4, 6, 8$, for a total of $3$ moments.

Sample Explanation 2

The instrument periods are $2$, $3$, $5$, and $6$ seconds. Within the first $20$ seconds, the moments when exactly $3$ instruments make sounds simultaneously are shown in the table below:

Explanation: the least common multiple of instruments $1$, $2$, and $4$ is $6$, so at times $6, 12, 18$ these three instruments will make sounds at the same time. Instrument $3$ (period $5$) does not make a sound at these times, so there are exactly $3$ instruments.

Constraints and Notes for Test Cases

For $30\%$ of the test cases, $N \leq 5$, $T \leq 100$.

For $60\%$ of the test cases, $N \leq 10$, $T \leq 1000$.

For all test cases, $1 \leq N \leq 20$, $1 \leq T \leq 10000$, $1 \leq K \leq N$, $1 \leq p_i \leq 100$.

Translated by ChatGPT 5