The winter months are soon approching, so Eric decides to prepare to pick some (a non-zero value) of the apples from his apple trees for his relatives, and leave the rest to sell to the supermarket. He has ~M~ baskets, one for each of his relatives, and he wants to keep ~K~ of the apples for himself to eat throughout the winter. Eric doesn't want his relatives to fight over the apples, so he plans to give each of them the same number of apples. Also, to keep his OCD in check, he will pick the same amount of apples from each of his ~N~ trees. From previous years of harvests, Eric knows that the maximum number of apples that are grown by each of his apple trees are ~X~. How many different total numbers of apples can he pick from each tree that satisfy the above conditions?

Subtasks

~1 \leq X \leq 10^9~

~1 \leq N,M \leq 10^6~

~1 \leq K \leq N~

~M~ is guaranteed to be prime.

Subtask 1 [30%]

~1 \leq X \leq 10^6~

~1 \leq N,M \leq 10^3~

Subtask 2 [70%]

No further constraints.

Input Specifications

The first and only line will contain an space-separated integers, ~N,K,M,X~.

Output Specifications

Output a single integer that represents the amount of different total of number of apples Eric can pick that satisfy the conditions in the problem.

Sample Input 1

2 1 7 15

Sample Output 1

2

Explanation for Sample Output 1

By picking ~4~ or ~11~ apples from each of the ~2~ trees, you can assure that each of his ~7~ relatives has an equal number of apples in their basket, while keeping the best apple to himself.

Sample Input 2

27 16 101 1000

Sample Output 2

10