Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Mr. Bender and Square

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputMr. 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* ≤ 10^{9}; 1 ≤ *x*, *y* ≤ *n*; *c* ≤ *n*^{2}).

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. .

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/13/2018 12:54:45 (d3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|