You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

迅风种下了一粒种子。起初，种子的成长值为 $0$，当某一天过完后，它的成长值大于等于 $k$ 时，则代表它已经破土而出。

从第 $1$ 天开始，种子会开始生长。原本这粒种子在第 $i$ 天会增加 $\lfloor\frac{i}{w}\rfloor$ 的成长值，但由于各种因素的干扰，从第 $x$ 天开始（包含第 $x$ 天），它每天都会额外增加 $y$ 的成长值。

请你求出这粒种子是在第几天破土而出的。

提示：$\lfloor x \rfloor$ 表示取不大于 $x$ 的最大整数。例如 $\lfloor 2.5 \rfloor = 2$。在 C++ 中，可以使用 floor 函数进行向下取整。例如 floor(2.9)=2，函数返回值为浮点型。对于本题，在 C++ 中，$\lfloor\frac{i}{w}\rfloor$ 可以用 int(i/w) 表示。

输入格式

一行四个正整数 $x,y,w,k$，含义见题面。

输出格式

一行一个正整数 $p$ 表示种子在第 $p$ 天结束时破土而出。

2 2 2 5

3

1000 1 3 1542

97

提示

样例解释 #1

第 $1$ 天成长值为：$0+\lfloor\frac{1}{2}\rfloor=0$，
第 $2$ 天成长值为：$0+(\lfloor\frac{2}{2}\rfloor+2)=3$，
第 $3$ 天成长值为：$3+(\lfloor\frac{3}{2}\rfloor+2)=6$。 因此该种子在第 $3$ 天结束时破土而出。

数据范围

对于前 $20\%$ 的数据，满足种子在第 $x$ 天以内（包含第 $x$ 天）破土而出。

对于前 $50\%$ 的数据，满足 $1\le x,k,w\le 1000$，$0\le y \le 1000$。

对于 $100\%$ 的数据，满足 $1\le x,k,w\le 10^6$，$0\le y \le 10^6$。