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。在第二个测试中,所有事件将如图所示进行。 。