Watering

Interview

Time limit1sMemory limit512 MB

Summary

Each day water A consecutive pots adding B moisture, then every pot loses 1; find the latest day the first plant can die with optimal watering.

Level: Medium6 of 10
Topics: Greedy, Sliding window, Prefix sum, Implementation
Solved: No attempts yet

Problem

Rangi the gardener wants to grow catnip, which cats are said to love.

One catnip plant is planted in each of $N$ flowerpots arranged in a straight line.

Each pot initially holds $K$ units of moisture, and every day the following happens in order.

Rangi waters $A$ consecutive pots. The moisture of each watered pot increases by $B$ .
The moisture of every pot decreases by 1.
The catnip in any pot whose moisture reaches 0 dies.

Write a program that prints the day the first catnip dies when the plants are watered so that all of them stay alive for as long as possible. The first day is day 1.

Input

The first line gives the natural numbers $N$ , $K$ , $A$ , and $B$ , separated by spaces. ( $2 \le N \le 100$ , $1 \le K \le 100$ , $1 \le A \times B < N$ , and $A$ divides $N$ )

Output

Print the day the first catnip dies when the plants are watered so that all of them stay alive for as long as possible.

Examples2

Example 1
Input
```
6 3 2 2
```
Expected output
```
5
```
Example 2
Input
```
2 2 1 1
```
Expected output
```
3
```