题目描述

小明在学习音乐，他发现不同乐器的演奏需要配合不同的节拍。现在有 $N$ 种乐器，每种乐器都有自己的“节拍周期”（以秒为单位）。

在音乐演奏中，如果某一时刻恰好是某个乐器节拍周期的整数倍，那么这个乐器就会在这一时刻发声。例如，一个节拍周期为 $3$ 秒的乐器会在第 $3$ 秒、第 $6$ 秒、第 $9$ 秒等时刻发声。

小明想知道：在前 $T$ 秒内（即第 $1$ 秒至第 $T$ 秒，包含第 $T$ 秒），恰好有 $K$ 种乐器同时发声的时刻有多少个？

输入格式

第一行包含三个整数 $N, T, K$，分别表示乐器数量、观察的时长、同时发声的乐器数量。

第二行包含 $N$ 个整数 $p_1, p_2, \dots, p_N$，表示每种乐器的节拍周期（单位：秒）。

输出格式

一行，输出一个整数，表示恰好有 $K$ 种乐器同时发声的时刻数量。

3 12 2
2 3 4

3

解释 #1

乐器周期分别为 $2$、$3$、$4$ 秒。在前 $12$ 秒内，每个时刻发声情况如下表所示：

表中“✓”表示该乐器在该时刻发声，“-”表示不发声。

恰好 $2$ 种乐器同时发声的时刻有：$t = 4, 6, 8$，共 $3$ 个。

4 20 3
2 3 5 6

3

解释 #2

乐器周期分别为 $2$、$3$、$5$、$6$ 秒。在前 $20$ 秒内，恰好 $3$ 种乐器同时发声的时刻如下表所示：

说明：乐器 $1$、$2$、$4$ 的最小公倍数为 $6$，所以在时刻 $6, 12, 18$ 这三个乐器会同时发声。乐器 $3$（周期 $5$）在这些时刻不发声，因此恰好 $3$ 种乐器。

5 100 1
7 11 13 17 19

36

数据范围

• 对于 $30\%$ 的评测用例，$N \leq 5$，$T \leq 100$；
• 对于 $60\%$ 的评测用例，$N \leq 10$，$T \leq 1000$；
• 对于所有评测用例，$1 \leq N \leq 20$，$1 \leq T \leq 10000$，$1 \leq K \leq N$，$1 \leq p_i \leq 100$。