A-Alpha, Beta, Omega_2023年第六届广西大学生程序设计竞赛（正式赛）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Slay the Spire is a game primarily about survival, collecting cards, and building a powerful deck to wipe out your foes.

Recently, Colin got interested in a special card : 'Alpha'.

Playing the 'Alpha' card will shuffle a 'Beta' into the draw pile.
Playing the 'Beta' card will shuffle an 'Omega' card into the draw pile.
Playing the 'Omega' card will generate the final Omega buff -- destroy your enemies, and achieve ultimate victory.

However, Colin always has poor luck during the game. So he wants to calculate at least how many rounds have been passed, no matter how bad his luck is, he will definitely win. To simplify the problem, we describe it as follows:

At the beginning, there are only $n_a$ 'Alpha' card , $n_b$ 'Beta' card and $n_o$ 'Omega' Card in the draw pile.

In each round, the system first randomly shuffles the entire draw pile, then Colin takes out $k\text{ }(k\le n_a + n_b + n_o )$ cards at the top of the draw pile:

If there are at least one 'Omega' card among the $k$ cards, Colin win the game immediately.
Otherwise, Colin will play the $k$ cards taken out in an arbitrary order. (Playing the 'Alpha' card will shuffle a 'Beta' into the draw pile. Playing the 'Beta' card will shuffle an 'Omega' card into the draw pile.)

Please calculate at least how many rounds have been passed, no matter how bad Colin's luck is, he will definitely win.

输入描述:

A single line contains four integers $n_a,n_b,n_o,k \text{ } (0 \le n_a, n_b, n_o \le 3 \times 10^8 , 1 \le k \le n_a + n_b + n_o)$ , representing there are $n_a$ 'Alpha' card , $n_b$ 'Beta' card and $n_o$ 'Omega' card in the initial draw pile, and $k$ is the number of cards should be taken out in each round.

输出描述:

A single integer, represents the minimum number of rounds guarantees that Colin will win.

示例1

输入

复制

3 0 0 2

输出

复制

说明

In the worst case, Colin can only get the 'Omega' card for the first time in the fourth round.

first round: Colin may take out two 'Alpha' card and shuffle two 'Beta' card into the draw pile.

second round: Colin may take out an 'Alpha' card and a 'Beta' card, then shuffle a 'Beta' card and an 'Omega' card into the draw pile.

third round: Colin may take out two 'Beta' card and shuffle two 'Omega' card into the draw pile.

fourth round: Now there are only three 'Omega' card in the draw pile. Colin takes out two 'Omega' card and win the game.

示例2

输入

复制

100000000 100000000 100000000 1

输出

复制

300000001