떨어진 수정

마나 수정 $M$개가 신 나무스트럼에 떨어졌다. 수정이 떨어진 뒤 시체가 되살아나 마을을 덮쳤고, 마을의 수장 Marko는 시체를 되살린 마법사 Kul'den을 사로잡았다. 심문 결과 $M$개의 마나 수정이 되살아난 시체에게 마나를 공급하고 있으며, 수정을 모두 파괴하면 시체가 멈춘다는 사실이 드러났다. 마을에는 둔 망치가 있고, 이 망치는 한 번에 마나 수정 하나에만 힘을 가한다.

Marko가 수정을 하나씩 부수던 도중 큰 폭발이 일어났다. 대 마법사 매디브가 원인을 분석해서, 마나가 크게 응집된 수정을 부수는 데 필요한 힘보다 훨씬 강한 힘으로 내리치면 응집된 마나가 과부하를 일으켜 폭발한다는 것을 밝혀냈다. 샤먼 타사다르는 남은 수정 $N$개를 감정해서, 그중 정확히 하나에만 마나가 응집되어 있고 그 수정이 $N$개 가운데 $K$번째로 강하다는 사실을 알아냈다. 즉 응집된 수정보다 강한 수정이 $K-1$개, 약한 수정이 $N-K$개 있다. 남은 수정의 강도는 모두 다르고 강도의 순서도 전부 알고 있지만, 강도의 실제 값은 아무도 모른다.

각 수정의 강도는 서로 다른 양의 실수이고 모두 $P$ 이하이다. 대장장이 린드홀은 $P$ 이하의 양의 실수 $p$를 마음속으로 정하면 수정에 정확히 $p$의 힘을 가할 수 있다. 강도가 $X$인 수정을 $X$ 이상의 힘으로 내리치면 그 수정은 부서져 사라지고, 사라진 수정은 다시 내리칠 수 없다. $X$ 미만의 힘으로 내리치면 아무 일도 일어나지 않는다. 마나가 응집된 수정만은 예외로, 강도보다 $W$ 이상 강한 힘, 즉 $X + W$ 이상의 힘으로 내리치면 폭발한다.

당신은 린드홀에게 몇 번째로 강한 수정을 얼마의 힘으로 내리칠지 한 번에 하나씩 명령하고, 그 수정이 부서졌는지 아닌지는 바로 알 수 있다. 폭발이 일어날 가능성이 조금이라도 있는 명령은 내릴 수 없다. 강도가 어떻게 정해져 있든 폭발 없이 응집된 수정을 반드시 부수면서, 내리치는 횟수의 최댓값을 가장 작게 만드는 전략을 쓰려고 한다. 이 전략을 썼을 때 최악의 경우 망치를 내리치는 횟수를 구하여라.

첫째 줄에 정수 $N$, $K$, $P$, $W$가 공백으로 구분되어 주어진다. 차례대로 남아 있는 마나 수정의 수 $N$, 마나가 응집된 수정의 강도 순위 $K$, 둔 망치의 최대 파워 $P$, 폭발이 일어나는 힘의 차이 $W$를 뜻한다. ($1 \le N \le 1000$, $1 \le K \le N$, $1 \le P \le 2000$, $1 \le W \le P$)

조건을 만족하도록 각 수정의 강도를 정할 수 없는 입력은 주어지지 않는다.

최악의 경우 내리치는 횟수를 최소로 만드는 전략을 썼을 때, 마나가 응집된 수정이 부서질 때까지 망치를 내리치는 최대 횟수를 한 줄에 출력한다.