题目描述

为了举办一场竞赛，提出了 $N$ 道题目。最初，第 $i$ 道题目的分数为整数 $A_i$。

接下来，有 $M$ 名评委将对自己喜欢的题目进行投票。每位评委独立地恰好选择 $V$ 道题目，并将这些题目的分数各增加 $1$。

所有 $M$ 名评委投票结束后，将 $N$ 道题目按分数从高到低排序，前 $P$ 道题目将被选为竞赛的题目集合。对于分数相同的题目，其顺序由评委长任意决定。

在 $N$ 道题目中，有多少道题目有可能被选入题目集合？

输入格式

输入以如下格式从标准输入读入。

$N$ $M$ $V$ $P$ $A_1$ $A_2$ $...$ $A_N$

输出格式

输出有可能被选入题目集合的题目的数量。

样例 1

输入

6 1 2 2
2 1 1 3 0 2

输出

5

样例 2

输入

6 1 5 2
2 1 1 3 0 2

输出

3

样例 3

输入

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

输出

8

说明/提示

限制条件

• $2 \leq N \leq 10^5$
• $1 \leq M \leq 10^9$
• $1 \leq V \leq N-1$
• $1 \leq P \leq N-1$
• $0 \leq A_i \leq 10^9$

样例解释 1

如果唯一的评委对第 $2$、$5$ 题投票，则每题的分数变为 $2\ 2\ 1\ 3\ 1\ 2$，第 $4$ 题，以及第 $1,2,6$ 题中的 $1$ 题会被选中。如果评委对第 $3,4$ 题投票，则每题的分数变为 $2\ 1\ 2\ 4\ 0\ 2$，第 $4$ 题，以及第 $1,3,6$ 题中的 $1$ 题会被选中。因此，第 $1,2,3,4,6$ 题有可能被选中，而第 $5$ 题不可能被选中。

样例解释 2

有可能被选中的只有第 $1,4,6$ 题。

由 ChatGPT 4.1 翻译