#include <bits/stdc++.h>
using namespace std;
template <class T>
inline T bigmod(T p, T e, T M) {
  long long int ret = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) ret = (ret * p) % M;
    p = (p * p) % M;
  }
  return (T)ret;
}
template <class T>
inline T gcd(T a, T b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
template <class T>
inline T modinverse(T a, T M) {
  return bigmod(a, M - 2, M);
}
template <class T>
inline T bpow(T p, T e) {
  long long int ret = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) ret = (ret * p);
    p = (p * p);
  }
  return (T)ret;
}
int toInt(string s) {
  int sm;
  stringstream ss(s);
  ss >> sm;
  return sm;
}
int toLlint(string s) {
  long long int sm;
  stringstream ss(s);
  ss >> sm;
  return sm;
}
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int ln1[4][2] = {2, 3, 3, 0, 0, 1, 1, 2};
int l[4][4];
bool bl[4];
int n, x, y;
long long int sm;
void chng(int i) {
  l[i][0] += dx[ln1[i][0]];
  l[i][1] += dy[ln1[i][0]];
  l[i][2] += dx[ln1[i][1]];
  l[i][3] += dy[ln1[i][1]];
  if (l[i][0] < 1 || l[i][0] > n || l[i][1] < 1 || l[i][1] > n) {
    l[i][0] -= dx[ln1[i][0]];
    l[i][1] -= dy[ln1[i][0]];
    l[i][0] += dx[ln1[i][1]];
    l[i][1] += dy[ln1[i][1]];
    if (l[i][0] < 1 || l[i][0] > n || l[i][1] < 1 || l[i][1] > n) {
      bl[i] = 0;
      return;
    }
  }
  if (l[i][2] < 1 || l[i][2] > n || l[i][3] < 1 || l[i][3] > n) {
    l[i][2] -= dx[ln1[i][1]];
    l[i][3] -= dy[ln1[i][1]];
    l[i][2] += dx[ln1[i][0]];
    l[i][3] += dy[ln1[i][0]];
    if (l[i][2] < 1 || l[i][2] > n || l[i][3] < 1 || l[i][3] > n) {
      bl[i] = 0;
      return;
    }
  }
}
int main() {
  int cs = 1, t, i, j, k, rs;
  scanf("%d%d%d", &n, &x, &y);
  cin >> sm;
  sm--;
  for (i = 0; i < 4; i++) {
    for (j = 0; j < 2; j++) {
      l[i][2 * j] = x;
      l[i][2 * j + 1] = y;
    }
    bl[i] = 1;
  }
  for (rs = 0; sm > 0; rs++) {
    for (i = 0; i < 4; i++) {
      if (bl[i]) chng(i);
    }
    for (i = 0; i < 4; i++) {
      if (!bl[i]) continue;
      sm -= (min(abs(l[i][0] - l[i][2]), abs(l[i][1] - l[i][3])) + 1LL);
      if (bl[(i + 1) % 4] == 1 && l[i][2] == l[(i + 1) % 4][0] &&
          l[i][3] == l[(i + 1) % 4][1])
        sm++;
    }
  }
  printf("%d\n", rs);
  return 0;
}

### Prompt

Your challenge is to write a Cpp solution to the following problem:

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <class T>
inline T bigmod(T p, T e, T M) {
  long long int ret = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) ret = (ret * p) % M;
    p = (p * p) % M;
  }
  return (T)ret;
}
template <class T>
inline T gcd(T a, T b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
template <class T>
inline T modinverse(T a, T M) {
  return bigmod(a, M - 2, M);
}
template <class T>
inline T bpow(T p, T e) {
  long long int ret = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) ret = (ret * p);
    p = (p * p);
  }
  return (T)ret;
}
int toInt(string s) {
  int sm;
  stringstream ss(s);
  ss >> sm;
  return sm;
}
int toLlint(string s) {
  long long int sm;
  stringstream ss(s);
  ss >> sm;
  return sm;
}
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int ln1[4][2] = {2, 3, 3, 0, 0, 1, 1, 2};
int l[4][4];
bool bl[4];
int n, x, y;
long long int sm;
void chng(int i) {
  l[i][0] += dx[ln1[i][0]];
  l[i][1] += dy[ln1[i][0]];
  l[i][2] += dx[ln1[i][1]];
  l[i][3] += dy[ln1[i][1]];
  if (l[i][0] < 1 || l[i][0] > n || l[i][1] < 1 || l[i][1] > n) {
    l[i][0] -= dx[ln1[i][0]];
    l[i][1] -= dy[ln1[i][0]];
    l[i][0] += dx[ln1[i][1]];
    l[i][1] += dy[ln1[i][1]];
    if (l[i][0] < 1 || l[i][0] > n || l[i][1] < 1 || l[i][1] > n) {
      bl[i] = 0;
      return;
    }
  }
  if (l[i][2] < 1 || l[i][2] > n || l[i][3] < 1 || l[i][3] > n) {
    l[i][2] -= dx[ln1[i][1]];
    l[i][3] -= dy[ln1[i][1]];
    l[i][2] += dx[ln1[i][0]];
    l[i][3] += dy[ln1[i][0]];
    if (l[i][2] < 1 || l[i][2] > n || l[i][3] < 1 || l[i][3] > n) {
      bl[i] = 0;
      return;
    }
  }
}
int main() {
  int cs = 1, t, i, j, k, rs;
  scanf("%d%d%d", &n, &x, &y);
  cin >> sm;
  sm--;
  for (i = 0; i < 4; i++) {
    for (j = 0; j < 2; j++) {
      l[i][2 * j] = x;
      l[i][2 * j + 1] = y;
    }
    bl[i] = 1;
  }
  for (rs = 0; sm > 0; rs++) {
    for (i = 0; i < 4; i++) {
      if (bl[i]) chng(i);
    }
    for (i = 0; i < 4; i++) {
      if (!bl[i]) continue;
      sm -= (min(abs(l[i][0] - l[i][2]), abs(l[i][1] - l[i][3])) + 1LL);
      if (bl[(i + 1) % 4] == 1 && l[i][2] == l[(i + 1) % 4][0] &&
          l[i][3] == l[(i + 1) % 4][1])
        sm++;
    }
  }
  printf("%d\n", rs);
  return 0;
}

```