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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;


public class Main {
    static ArrayList<Integer>[] arreglos;
    static int length;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] r=br.readLine().split(" ");
        int n=Integer.parseInt(r[0]);
        int x=Integer.parseInt(r[1])-1;
        int y=Integer.parseInt(r[2])-1;
        long c=Long.parseLong(r[3]);
        int res=f(n,x,y,c);
        System.out.println(res);
    }
    public static int f(int n, int x, int y, long c) {
        int min=1;
        while (true){
            long res=simular(n,x,y,min);
            if (res>=c){
                break;
            }
            min*=2;
        }
        return binarySearch(n,x,y,c,0,min);
    }
    public static int binarySearch(int n, int x, int y, long c, int i, int j) {
        if (i==j){
            return i;
        }
        int med=(i+j)/2;
        long res=simular(n, x, y, med);
        if(res<c){
            return binarySearch(n,x,y,c,med+1,j);
        }
        else{
            return binarySearch(n,x,y,c,i,med);
        }
    }
    public static long simular(int n, int x, int y, int radio){
        long res=0;
        for (int i=(x-radio);i<=(x+radio);i++){
            if (i<0 || i>=n){
                continue;
            }
            long distance=Math.abs(i-x);
            long pv=radio-distance;
            long arriba=Math.min(pv,n-1-y);
            long abajo=Math.min(pv,y);
            res=res+arriba+abajo+1;
        }
        return res;
    }
}