Farmer Bob is buying cereal boxes at his local grocery store, which are priced in the following way:

• The first ~M~ cereal boxes cost ~C~ dollars each
• For every ~M~ boxes purchased, the price of any subsequent boxes is increased by ~I~ dollars

Bob only has ~Q~ dollars to spend. What is the maximum number of cereal boxes he can buy?

Constraints

For all subtasks:

• ~1 \le M, C, I \le 10^9~
• ~1 \le Q \le 10^{12}~

Input Specification

The only line of input contains four integers ~M~, ~C~, ~I~ and ~Q~.

Output Specification

Output the maximum number of cereal boxes Bob can buy.

Sample Input 1

2 1 3 35

Sample Output 1

7

Explanation for Sample 1

The prices of the cereal boxes Bob can buy are ~1~, ~1~, ~4~, ~4~, ~7~, ~7~ and ~10~ dollars respectively.

Sample Input 2

1 15 1 10

Sample Output 2

0