ami đang chơi game bắn súng. Hiện tại có \(n\) ải, mỗi ải có \(c_i\) con boss. Cây súng của ami khi bắt đầu trò chơi sẽ có \(W\) viên đạn và sức chứa tối đa là \(W\) viên đạn. ami sẽ tốn \(d_i\) viên đạn nếu muốn giết một con boss ở ải \(i\). Khi giết được một con boss thì sức chứa tối đa của cây súng được tăng lên \(Y\). Khi qua một ải mới, ami sẽ hồi \(T\) viên đạn. Đương nhiên, số viên đạn sẽ không thể vượt quá sức chứa tối đa của cây súng.

ami không cần giết hết quái của 1 ải trước khi qua ải mới, và ami chỉ tiến lên ải mới chứ không lùi, bắt đầu từ ải 1. Hãy tính số lượng boss tối đa mà ami có thể tiêu diệt.

Input

• Dòng đầu tiên chứa 4 số nguyên \(n\), \(W\), \(Y\), \(T\) là số ải, sức chứa và số viên đạn ban đầu, sức chứa cộng thêm khi tiêu diệt 1 boss và số viên đạn phục hồi khi qua ải mới.
• Dòng tiếp theo chứa \(n\) số nguyên \(c_i\) là số con boss ở ải \(i\).
• Dòng cuối cùng chứa \(n\) số nguyên \(d_i\) là số viên đạn cần dùng để diệt một con boss ở ải \(i\).

Output

• Một số nguyên là số boss nhiều nhất diệt được.

Example

2 5 0 0
3 4
2 1

4

2 5 5 5
3 4
5 5

2

Scoring

• \(100\%\) test có \(1 \leq n \leq 3000\), \(\sum c_i \leq 10^4\) và \(0 \leq d_i, W, Y, T \leq 10^9\).