Лотерея

시간 제한1초메모리 제한1024 MB

요약

구간 [a, b]의 각 정수에 대해 주어진 n개의 수 중 몇 개가 그 수를 나누는지 세고, 정확히 k개로 나누어지는 정수의 개수를 구한다.

난이도: 보통10점 중 6점
유형: 조합론, 수학, 정수론, 완전 탐색
정답자: 아직 제출이 없습니다

문제

Планета Шелезяка. Воды нет. Полезных ископаемых нет. Населена роботами.

Недавно на планету Шелезяка прибыла новая партия чистейшей смазки. К сожалению, на всех ее не хватает. Поэтому было решено провести лотерею. Для этого было выбрано $n$ натуральных чисел $a\_1, a\_2 \ldots a\_n$ и число $k$ , $0 \le k \le n$ . Cмазку получат те роботы, серийные номера которых делятся ровно на $k$ из этих чисел.

Теперь правительство заинтересовало то, насколько равномерно распределены призы. Для этого они решили выяснить, какое число роботов, серийные номера которых принадлежат промежутку $\[a..b]$ , получат смазку.

입력

В первой строке входного файла заданы натуральные числа $n$ ( $1 \le n \le 10^5$ ) и $k$ ( $0 \le k \le n$ ). Во второй строке входного файла перечислены $n$ натуральных $a\_1, a\_2 \ldots a\_n$ , разделенные пробелами. Каждое из этих $a\_i$ не превосходит $10^{9}$ . В третьей строке входного файла задано два натуральных числа $a$ и $b$ ( $1 \le a \le b \le 10^{9}$ , $b - a \le 10^5$ ).

출력

В выходной файл выведите количество чисел из промежутка $\[a..b]$ , которые делятся ровно на $k$ данных чисел.

예제2

예제 1
입력
```
2 1
2 3
1 10
```
예상 출력
```
6
```
예제 2
입력
```
4 2
2 3 4 5
10 30
```
예상 출력
```
5
```