새들

봉제 인형 외에도, Imp는 작고 노란 새들을 무척 좋아한다!

새를 소환하려면 Imp에게 강력한 마법이 필요하다. 공원의 한 오솔길을 따라 n그루의 나무가 일렬로 늘어서 있고, 각 나무에는 둥지가 하나씩 있다. i-th 둥지에는 새가 ci마리 있으며, 이 둥지에서 새 한 마리를 소환하려면 Imp가 이 나무 아래에 있어야 하고 마나 costi포인트를 소모해야 한다. 그러나 새를 한 마리 소환할 때마다 Imp의 마나 용량은 B포인트 증가한다. Imp는 새를 한 마리씩 소환하며, i-th 둥지에서 0마리부터 ci마리까지 원하는 수의 새를 소환할 수 있다.

Initially Imp는 첫 번째 나무 아래에 있으며 마나를 W포인트 가지고 있고, 마나 용량 역시 W이다. 그는 앞으로만 이동할 수 있으며, 한 나무에서 다음 나무로 이동할 때마다 마나를 X포인트 회복한다(단, 현재 마나 용량을 초과할 수 없다). 앞으로만 이동할 때, Imp가 소환할 수 있는 새의 최대 수는 얼마인가?

첫 번째 줄에는 네 정수 n, W, B, X (1 ≤ n ≤ 103, 0 ≤ W, B, X ≤ 109)가 주어진다. 각각 나무의 수, 초기 마나 포인트, 새를 한 마리 소환한 후 증가하는 마나 용량의 포인트 수, Imp가 한 나무에서 다음 나무로 이동할 때 회복되는 포인트 수를 나타낸다.

두 번째 줄에는 n개의 정수 c1, c2, ..., cn (0 ≤ ci ≤ 104)가 주어진다. 여기서 ci는 i-th 둥지에 사는 새의 수이다. 임이 보장된다.

세 번째 줄에는 n개의 정수 cost1, cost2, ..., costn (0 ≤ costi ≤ 109)가 주어진다. 여기서 costi는 i-th 둥지에서 새 한 마리를 소환하는 데 드는 마나 비용이다.

Imp가 소환할 수 있는 새의 최대 수를 나타내는 정수 하나를 출력한다.

첫 번째 예제에서 Imp의 기본 마나량은 12이며, 최대 용량도 12이다. 첫 번째 둥지에서 새 두 마리를 소환한 후에는 마나를 8포인트 잃지만, 최대 용량은 (since B = 0) 증가하지 않는다. 이 단계가 끝나면 마나는 12 중 4가 된다. 이동하는 동안 마나를 4포인트 회복하므로, 가능한 12 중 8의 마나를 보유하게 된다. 이제 두 번째 둥지에서 새 4마리를 소환하고 마나 8을 소모하는 것이 최적이다. 최종 답은 — 6이다.

두 번째 예제에서 기본 마나량은 1000이다. 마지막 둥지의 새를 모두 소환하기만 하는 것이 올바른 선택이다. Imp의 마나는 처음부터 가득 차 있으므로 이동하는 동안 회복되지 않는다는 점에 유의한다.