该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

You are given an array $a$ of length $n$ and a positive integer $S$.

Define a function $g(l,r)$ as : Ask if there is a subset whose sum is $S$ in $a_la_{l+1}...a_{r}$. If such a subset exists, the answer $g(l, r)$ is equal to $1$, otherwise $g(l,r)$ is equal to $0$.

Now, You are given two integers $m, k$. Consider you have a window of length $m$ starting from $1$, and each time the window slides $k$ units to the right. It is guaranteed that $n - m$ is divisible by $k$.

Your task is to calculate $\sum\limits_{i=0}^{\frac{n-m}{k}}g(i\times k+1,i\times k + m)$.

输入格式

The first line contains four integers $n,m,k, S$ $(1 \leq k \leq m \leq n \leq 2\times10^4, 1\leq S \leq 10^3)$.

The second line contains $n$ integers $a_1, a_2,...,a_n$ $(1 \leq a_i \leq 10^3)$ $-$ the value of $a_i$.

It is guaranteed that $n - m$ is divisible by $k$.

输出格式

Print the answer a line.

样例

7 3 2 10
1 2 3 4 3 6 7

2

样例

10 4 2 8
4 3 2 1 5 7 4 1 2 5

4

提示

In the first example, it is not difficult to find the answer is $g(1, 3) + g(3, 5) + g(5, 7) = 0 + 1 + 1 = 2$.