A. Alpha, Beta, Omega
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Slay the Spire is a game about survival, collecting cards, and building a powerful deck to defeat your enemies. Recently, Colin has become interested in a special card called Alpha.

  • Playing an Alpha card shuffles a Beta card into the draw pile.
  • Playing a Beta card shuffles an Omega card into the draw pile.
  • Playing an Omega card grants the final Omega buff, allowing Colin to defeat his enemies and win.

Unfortunately, Colin is always unlucky. He wants to know when victory is guaranteed, even under the worst possible sequence of shuffles.

The process is simplified as follows. Initially, the draw pile contains only $$$n_a$$$ Alpha cards, $$$n_b$$$ Beta cards, and $$$n_o$$$ Omega cards. In each round:

  • The entire draw pile is shuffled, and Colin draws the top $$$k$$$ cards.
  • If at least one of the drawn cards is an Omega card, Colin wins immediately.
  • Otherwise, Colin plays all $$$k$$$ drawn cards. Each played Alpha card is removed and adds one Beta card to the draw pile; each played Beta card is removed and adds one Omega card to the draw pile. Newly added cards cannot be drawn until a later round.

Find the minimum number of rounds after which Colin is guaranteed to have won, regardless of how unlucky the shuffles are.

Input

A single line contains four integers $$$n_a$$$, $$$n_b$$$, $$$n_o$$$, and $$$k$$$ ($$$0 \le n_a,n_b,n_o \le 3 \times 10^8$$$, $$$1 \le k \le n_a+n_b+n_o$$$).

The first three integers are the initial numbers of Alpha, Beta, and Omega cards, respectively. Colin draws exactly $$$k$$$ cards in each round.

Output

Output a single integer: the minimum number of rounds after which Colin is guaranteed to have won.

Examples
Input
3 0 0 2
Output
4
Input
100000000 100000000 100000000 1
Output
300000001
Note

In the first example, the worst case proceeds as follows:

First round: Colin may draw two Alpha cards and shuffle two Beta cards into the draw pile.

Second round: Colin may draw one Alpha card and one Beta card, then shuffle one Beta card and one Omega card into the draw pile.

Third round: Colin may draw two Beta cards and shuffle two Omega cards into the draw pile.

Fourth round: The draw pile now contains only three Omega cards, so Colin draws an Omega card and wins.

Therefore, in the worst case, Colin first draws an Omega card in the fourth round.