등산

리투아니아 등산객 비타스(Vytis)는 오늘 산책을 하려고 한다. 그는 지형도를 보고 각 지점의 고도 순서로 나타낸 경로를 골랐다. i번째 지점에서 i + 1번째 지점으로 갈 때, 비타스는 고도 차이만큼 오르거나 내려간다. 두 지점의 고도가 같으면 곧바로 걷는다. 비타스는 해수면(고도 0)에서 출발해 해수면에서 끝낸다.

비타스는 1미터를 걷거나 오르거나 내려가는 데 1 시간 단위가 걸린다. 에너지는 다음과 같이 변한다.

• 아침을 먹으면 에너지가 $E_0$가 된다.
• 1미터를 오를 때마다 에너지를 $E_u$만큼 소모한다.
• 1미터를 내려갈 때마다 에너지를 $E_n$만큼 소모한다.
• 곧바로 걸을 때는 에너지를 소모하지 않는다. 다만 에너지가 전혀 없으면 곧바로 걸을 수 없다.
• 산행 중 에너지를 모두 쓰면 앉아서 쉰다. 쉬는 동안에는 1 시간 단위마다 에너지를 $E_g$만큼 얻는다.

예를 들어 $E_0 = 6$, $E_u = 3$, $E_n = 1$, $E_g = 1$이라고 하자. 비타스는 아래 그림과 같은 산을 오르려고 한다.

그림 1. 오른쪽은 고도를 나타내고, 그림 아래에는 경로의 지점이 적혀 있다.

1. 첫 번째 지점까지 1 시간 동안 올라가며 에너지 3을 쓴다.
2. 두 번째 지점까지 1 시간 동안 올라가며 에너지 3을 쓴다.
3. 에너지가 없으므로 여기서 쉰다. 쉬고 나면 에너지 1을 얻으며, 쉬는 데 1 시간이 걸린다.
4. 세 번째 지점까지 1 시간 동안 곧바로 걷는다. 에너지는 쓰지 않는다.
5. 에너지가 부족해 세 번째 지점에서 내려갈 수 없으므로 1 시간 더 쉰다.
6. 세 번째 지점에서 내려간다. 2 시간이 걸리고 에너지 2를 쓴다.

따라서 비타스는 7 시간 동안 이동하며, 그중 5 시간은 걷거나 오르내리고 2 시간은 쉰다.

비타스가 아침을 먹고 출발한다고 할 때, 이 산행이 몇 시간 걸리는지 구하라.

첫 줄에는 네 정수 $E_0$, $E_u$, $E_n$, $E_g$가 주어진다. 각각 다음을 뜻한다.

• $E_0$: 아침을 먹은 뒤 비타스의 에너지
• $E_u$: 1미터 오를 때 소모하는 에너지
• $E_n$: 1미터 내려갈 때 소모하는 에너지
• $E_g$: 쉬는 1 시간 단위마다 얻는 에너지

둘째 줄에는 경로의 길이 $N$이 주어진다. 이어지는 $N$개 줄에는 고도 $h_i$가 차례로 주어진다.

산행이 걸리는 시간 단위의 수를 나타내는 정수 하나를 출력한다.

• $1 \le E_0, E_g, E_u, E_n \le 1\,000$
• $1 \le N \le 100\,000$
• $1 \le h_i \le 10\,000$