28451번 - 모기 킬러

문제

하얔이는 R동에서 T동까지 이동하려고 한다. 하지만 가는 도중에 모기가 너무 많아 이동하기에 어려움을 겪고있다. 하얔이는 모기를 퇴치하기 위해 모기 스프레이를 준비했다. 스프레이를 분사할 경우 하얔이의 현재 위치가 $x$라고 했을 때, $[x+1, x+A]$ 범위에 있는 모든 모기에게 $B$만큼의 피해를 준다. $i$번 모기는 위치 $d_i$와 체력 $h_i$를 가지며 체력이 0ドル$ 이하가 된 모기는 사라진다. 모기는 하얔이가 행동을 진행한 후 1ドル$만큼 하얔이를 향해 다가온다. 하얔이는 모기를 매우 싫어하기 때문에 모기와의 거리가 0ドル$이 되는 순간 T동까지 이동하기를 포기한다.

하얔이는 매 시간마다 다음과 같은 행동 중 하나를 수행해야 한다.

• R동을 향해 1ドル$만큼 이동한다. 하얔이가 이미 R동에 위치해있다면 선택할 수 없다.
• T동을 향해 1ドル$만큼 이동한다.
• 모기 스프레이를 분사한다.

R동의 위치는 0ドル,ドル T동의 위치는 $L$이다.

하얔이가 T동으로 가는 최소 시간을 구해보자.

입력

첫째 줄에 모기의 수 $N$과 T동의 위치 $L$이 공백으로 구분되어 정수로 주어진다. $(1 \leq N, L \leq 100,000円)$

둘째 줄에 스프레이의 범위 $A$와 스프레이의 피해량 $B$가 공백으로 구분되어 정수로 주어진다. $(1 \leq A \leq 10; 1 \leq B \leq 100,000円)$

셋째 줄에 $i$번 모기의 위치를 나타내는 길이 $N$ 수열 $d$가 공백으로 구분되어 정수로 주어진다. $(1 \leq d_i \leq L)$

넷째 줄에 $i$번 모기의 체력을 나타내는 길이 $N$ 수열 $h$가 공백으로 구분되어 정수로 주어진다. $(1 \leq h_i \leq 100,000円)$

출력

첫째 줄에 하얔이가 T동에 도착하는 최소 시간을 출력한다. 만약 도착할 수 없다면, $-1$을 출력한다.

제한

힌트