Snow loves taking pictures of snow. Unfortunately, it's not snowing yet... Thus, she turns to the one tool that everyone loves: Generative AI!

After uploading ~N~ of her pictures, Snow prompts the AI:

make snowy pls

and it outputs snowy versions of all her photos. Snow decides to give each picture a rating to see which pictures are best to keep. However, she notices the AI-generated photos keep getting better and better!

Amazed, she looks back at her ratings, discovering that they form an arithmetic sequence. The first photo has a rating of ~A~ points, and each successive photo generated is ~B~ points higher than the previous.

Since Snow wants all her photos to be great, she decides to continuously regenerate photos until all of them are greater than the snow threshold ~R~. Since she already used the AI, the first regenerated photo will have a new rating ~B~ points higher than the ~N~-th photo uploaded. The pattern will continue, with each successive photo generated having a new rating of ~B~ points higher than the previous.

What is the minimum number of times Snow has to reupload photos such that all of them have a rating greater than the snow threshold ~R~?

Constraints

For all subtasks,

~1 \le N, A, B, R \le 10^9~

Subtask 1 [10%]

~1 \le N \le 10^6~

~A \ge 2~

~R~ is less than the rating of the ~N~-th photo.

Subtask 2 [20%]

~1 \le N \le 10^9~

~A \ge 2~

~R~ is less than the rating of the ~N~-th photo.

Subtask 3 [30%]

~1 \le N \le 10^3~

~1 \le R \le 10^6~

Subtask 4 [40%]

No additional constraints.

It is not required to pass previous subtasks to earn points for a specific subtask. Sample inputs will not be pretested.

Input Specification

The first and only line of input contains ~N~, ~A~, ~B~, and ~R~, space-separated.

Output Specification

Output one integer, the minimum number of times Snow has to reupload photos such that all of them have a rating greater than the snow threshold ~R~.

Sample Input 1

6 5 3 11

Sample Output 1

3

Explanation for Sample Output 1

Her 6 photos have the following ratings:

5 8 11 14 17 20

Snow needs to reupload the first three photos, thus the ratings become (maintaining the same order of photos):

23 26 29 14 17 20

all are greater than the snow threshold of ~11~.

Sample Input 2

4 2 1 15

Sample Output 2

14