#include <bits/stdc++.h>
using namespace std;
long long n, x, y, c;
int X[8];
int Y[8];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
inline bool isValid(int x, int y) {
  return (x >= 1 && y >= 1 && x <= n && y <= n);
}
bool moveEnd(int &x, int &y, int mf, int ms) {
  int nx, ny;
  nx = x + dx[mf];
  ny = y + dy[mf];
  if (isValid(nx, ny)) {
    x = nx;
    y = ny;
    return true;
  }
  nx = x + dx[ms];
  ny = y + dy[ms];
  if (isValid(nx, ny)) {
    x = nx;
    y = ny;
    return true;
  }
  return false;
}
int dist(int a, int b) { return abs(a - b) + 1; }
int main() {
  int i, j;
  cin >> n >> x >> y >> c;
  long long cur = 1;
  int res = 0;
  for (i = 0; i < 8; ++i) {
    X[i] = x;
    Y[i] = y;
  }
  while (cur < c) {
    for (i = 0; i < 4; ++i) {
      bool fl;
      fl = true;
      fl = (fl && moveEnd(X[2 * i], Y[2 * i], i, (i + 1) % 4));
      fl = (fl && moveEnd(X[2 * i + 1], Y[2 * i + 1], (i + 1) % 4, i));
      if (fl) cur += dist(X[2 * i], X[2 * i + 1]);
    }
    for (i = 1; i < 8; i += 2) {
      if (X[i] == X[(i + 1) % 8] && Y[i] == Y[(i + 1) % 8]) --cur;
    }
    res++;
  }
  cout << res << endl;
  return 0;
}

### Prompt

Please formulate 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;
long long n, x, y, c;
int X[8];
int Y[8];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
inline bool isValid(int x, int y) {
  return (x >= 1 && y >= 1 && x <= n && y <= n);
}
bool moveEnd(int &x, int &y, int mf, int ms) {
  int nx, ny;
  nx = x + dx[mf];
  ny = y + dy[mf];
  if (isValid(nx, ny)) {
    x = nx;
    y = ny;
    return true;
  }
  nx = x + dx[ms];
  ny = y + dy[ms];
  if (isValid(nx, ny)) {
    x = nx;
    y = ny;
    return true;
  }
  return false;
}
int dist(int a, int b) { return abs(a - b) + 1; }
int main() {
  int i, j;
  cin >> n >> x >> y >> c;
  long long cur = 1;
  int res = 0;
  for (i = 0; i < 8; ++i) {
    X[i] = x;
    Y[i] = y;
  }
  while (cur < c) {
    for (i = 0; i < 4; ++i) {
      bool fl;
      fl = true;
      fl = (fl && moveEnd(X[2 * i], Y[2 * i], i, (i + 1) % 4));
      fl = (fl && moveEnd(X[2 * i + 1], Y[2 * i + 1], (i + 1) % 4, i));
      if (fl) cur += dist(X[2 * i], X[2 * i + 1]);
    }
    for (i = 1; i < 8; i += 2) {
      if (X[i] == X[(i + 1) % 8] && Y[i] == Y[(i + 1) % 8]) --cur;
    }
    res++;
  }
  cout << res << endl;
  return 0;
}

```