31413번 - 입대

문제

드디어 병역의 의무를 질 나이가 된 용진이는 선진병영을 선도하는 대한민국 공군병 모집에 지원하고자 한다. 대한민국 공군 모집병으로 합격하기 위해선 가산점이 필요한데, 최근 높아진 공군의 인기 탓에 봉사활동 혹은 헌혈을 통해 $M$점 이상의 가산점을 모아야 한다.

현재 공군 지원일까지는 $N$일이 남았으며, 그중 $i$일에는 $s_i$점의 가산점을 얻을 수 있는 봉사활동에 참여할 수 있다. 헌혈은 1ドル$일부터 $N$일까지 아무 날짜에 할 수 있으며, 헌혈하는 경우 $A$점의 가산점을 획득한다. 단, 헌혈을 하는 경우 충분한 휴식을 위해 헌혈한 날을 포함하여 헌혈 이후 $D$일 동안 헌혈하거나 봉사활동에 참여할 수 없다.

헌혈이 무서웠던 용진이는 헌혈을 최대한 적게 하며 가산점을 $M$점 이상 모으고자 한다. 용진이를 도와 공군병 모집 마감일까지 $M$점 이상의 가산점을 모으기 위한 최소 헌혈 횟수를 구해주자.

입력

첫 번째 줄에 공군병 모집 마감일까지 남은 날짜 $N$과 합격하는 데 필요한 가산점을 의미하는 정수 $M$이 공백으로 구분되어 주어진다. $(1 \le N \le 1,000円;$ 1ドル \le M \le 10^7)$

두 번째 줄에 날짜마다 봉사활동에 참여해 얻을 수 있는 가산점을 의미하는 $N$개의 정수 $s_1,\cdots,s_N$이 공백으로 구분되어 주어진다. $(1 \le s_i \le 1,000円)$

세 번째 줄에 헌혈해서 얻을 수 있는 가산점을 의미하는 정수 $A$와 헌혈 후 휴식이 필요한 일수 $D$가 공백으로 구분되어 주어진다. $(1 \le A \le 10,000円;$ 1ドル \le D \le N)$

출력

최소 $M$점 이상의 가산점을 모으기 위해 필요한 최소 헌혈 횟수를 출력한다.

어떻게 해도 $M$점 이상의 가산점을 모을 수 없다면, -1을 출력한다.

제한

힌트