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. <image>.
import java.util.*;
import java.math.*;
import java.io.*;
public class b2 {
public static void main(String[] args) throws IOException
{
    input.init(System.in);
    int n = input.nextInt(), x = input.nextInt(), y = input.nextInt(),  c = input.nextInt();
    long lo = 0, hi = 2*n;
    while(hi > lo+1)
    {
        long mid = (hi+lo)/2;
        long covered = go(n, x, y, mid);
        if(covered < c)
            lo = mid;
        else hi = mid;
    }
    if(go(n, x, y, lo) < c) lo++;
    System.out.println(lo);
    
}
public static long go(int n, int x, int y, long d)
{
    long res = d*d + (d+1)*(d+1);
    long maxLeft = d - x;
    if(maxLeft >= 0) res -= (maxLeft+1)*(maxLeft+1);
    long maxTop = d - y;
    if(maxTop >= 0) res -= (maxTop+1)*(maxTop+1);
    long maxRight = d - (n+1-x);
    if(maxRight >= 0) res -= (maxRight+1)*(maxRight+1);
    long maxBot = d - (n+1-y);
    if(maxBot >= 0) res -= (maxBot+1)*(maxBot+1);
    long maxTopLeft = d - (x+y);
    if(maxTopLeft >= 0) res += (maxTopLeft+1)*(maxTopLeft+2)/2;
    long maxTopRight = d - ((n+1-x)+y);
    if(maxTopRight >= 0) res += (maxTopRight+1)*(maxTopRight+2)/2;
    long maxBotLeft = d - (x+(n+1-y));
    if(maxBotLeft >= 0) res += (maxBotLeft+1)*(maxBotLeft+2)/2;
    long maxBotRight = d - ((n+1-x)+(n+1-y));
    if(maxBotRight >= 0) res += (maxBotRight+1)*(maxBotRight+2)/2;
    return res;

}
public static class input {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    /** call this method to initialize reader for InputStream */
    static void init(InputStream input) {
        reader = new BufferedReader(
                     new InputStreamReader(input) );
        tokenizer = new StringTokenizer("");
    }

    /** get next word */
    static String next() throws IOException {
        while ( ! tokenizer.hasMoreTokens() ) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(
                   reader.readLine() );
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException {
        return Integer.parseInt( next() );
    }
    
    static double nextDouble() throws IOException {
        return Double.parseDouble( next() );
    }
}
}
