← 返回题目列表

Codeforces · 255/D

D. 本德尔先生和史克威尔

中文机器翻译题面 查看原题

Bender先生有一个大小为n×n的数字表,每个单元格都可以打开或关闭。他希望场上至少有 c 个已开启的方块。当这个条件满足时,本德尔先生就会很高兴。

我们将考虑从上到下从 1 到 n 编号的表行,以及从左到右从 1 到 n 编号的列。最初只有一个坐标为 (x, y)(x 是行号,y 是列号)的打开单元格,所有其他单元格都关闭。然后,每秒我们都会打开关闭的单元,但侧面相邻的单元却打开。

对于坐标为 (x, y) 的单元格,侧相邻单元格为坐标为 (x - 1, y)、(x + 1, y)、(x, y - 1)、(x, y + 1) 的单元格。

多少秒后本德尔先生会感到高兴?

输入

第一行包含四个空格分隔的整数 n、x、y、c (1 ≤ n, c ≤ 109; 1 ≤ x, y ≤ n; c ≤ n2)。

输出

在一行中打印一个整数——问题的答案。

示例

输入 #1

6 4 3 1

输出 #1

0

输入 #2

9 3 8 10

输出 #2

2

注意

最初,第一个测试有一个绘制的单元格,因此答案为 0。在第二个测试中,所有事件将如图所示进行。 。