跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F2601. Mr

  • ID: 2607
  • 传统题
  • 2000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:进阶
  • 上传者:
  • 二分
  • 模拟
  • 数学
  • 算法思想
  • 编程与模拟
  • 进阶
  • 难度
  • 共享题库
  • Codeforces
  • 英文题面
  • 题目来源
  • 题面语言

Mr

题目描述

D. Mr. Bender and Square
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Mr. Bender has a digital table of size n×n, each cell can be switched on or off. He wants the field to have at least c switched on squares. When this condition is fulfilled, Mr Bender will be happy.

We'll consider the table rows numbered from top to bottom from 1 to n, and the columns − numbered from left to right from 1 to n. Initially there is exactly one switched on cell with coordinates (x,y) (x is the row number, y is the column number), and all other cells are switched off. Then each second we switch on the cells that are off but have the side-adjacent cells that are on.

For a cell with coordinates (x,y) the side-adjacent cells are cells with coordinates (x-1,y), (x+1,y), (x,y-1), (x,y+1).

In how many seconds will Mr. Bender get happy?

Input

The first line contains four space-separated integers n,x,y,c (1≤n,c≤109;1≤x,y≤n;c≤n2).

Output

In a single line print a single integer − the answer to the problem.

Examples
Input
6 4 3 1
Output
0
Input
9 3 8 10
Output
2
Note

Initially the first test has one painted cell, so the answer is 0. In the second test all events will go as is shown on the figure. .


题目来源:fps-www.educg.net-codeforce-1-2833.xml.zip;FPS 共享题包,题包内第 2253 题。保留原作者与原赛事署名。