Baskets of Gold Coins

Interview

Time limit1sMemory limit128 MB

Summary

Given the total weight of coins drawn with counts 1..N-1 from N baskets, find which basket holds the lighter coins.

Level: Medium4 of 10
Topics: Math, Brute force, Implementation, Prefix sum
Solved: No attempts yet

Problem

You are given $N$ baskets of gold coins, numbered from $1$ to $N$ . In every basket except one, each gold coin weighs $w$ grams. In the single exceptional basket, each gold coin weighs $w - d$ grams and is therefore lighter than the others.

A wizard takes $1$ coin from Basket $1$ , $2$ coins from Basket $2$ , and so on, up to $N-1$ coins from Basket $N-1$ . He takes no coins from Basket $N$ . He then weighs all of the selected coins together and, from that single weighing, determines which of the $N$ baskets holds the lighter coins.

Emulate the wizard's computation.

Input

The input consists of one or more lines; each line describes one instance of the problem. Each line contains four positive integers separated by single spaces. The first three are $N$ , $w$ , and $d$ as described above, and the fourth is the weight obtained by weighing the selected coins.

$N$ is at least $2$ and at most $8000$ , $w$ is at most $30$ , and $d$ is smaller than $w$ .

Output

For each instance, print a single line containing one integer: the number of the basket that holds the lighter coins.

Examples4

Example 1

Input

10 25 8 1109
10 25 8 1045
8000 30 12 959879400

Expected output

2
10
50

Example 2
Input
```
2 30 10 20
```
Expected output
```
1
```
Example 3
Input
```
2 30 10 10
```
Expected output
```
2
```
Example 4
Input
```
100 20 5 98750
```
Expected output
```
50
```