#include <bits/stdc++.h>
using namespace std;
struct point {
  long long x, y;
};
long long my_abs(long long x) {
  if (x < 0) return -x;
  return x;
}
int inters_vert(long long n, long long x, long long y, long long dx,
                long long dy, long long X_VAL, point &p) {
  if ((x > X_VAL && dx < 0) || (x < X_VAL && dx > 0)) {
    long long diff = X_VAL - x;
    if (diff < 0) diff = -diff;
    long long new_y = y + diff * dy;
    if (new_y >= 1 && new_y <= n) {
      p.x = X_VAL;
      p.y = new_y;
      return 1;
    } else
      return 0;
  }
  return 0;
}
int inters_hor(long long n, long long x, long long y, long long dx,
               long long dy, long long Y_VAL, point &p) {
  if ((y > Y_VAL && dy < 0) || (y < Y_VAL && dy > 0)) {
    long long diff = Y_VAL - y;
    if (diff < 0) diff = -diff;
    long long new_x = x + diff * dx;
    if (new_x >= 1 && new_x <= n) {
      p.x = new_x;
      p.y = Y_VAL;
      return 1;
    } else
      return 0;
  }
  return 0;
}
int get_near(long long n, long long x, long long y, long long dx, long long dy,
             long long &new_x, long long &new_y) {
  if (x >= 1 && x <= n && y >= 1 && y <= n) {
    new_x = x;
    new_y = y;
    return 1;
  }
  point vv[4], pp;
  int vv_len = 0;
  if (inters_vert(n, x, y, dx, dy, 1, pp)) vv[vv_len++] = pp;
  if (inters_vert(n, x, y, dx, dy, n, pp)) vv[vv_len++] = pp;
  if (inters_hor(n, x, y, dx, dy, 1, pp)) vv[vv_len++] = pp;
  if (inters_hor(n, x, y, dx, dy, n, pp)) vv[vv_len++] = pp;
  if (vv_len == 0) return 0;
  long long mn_dist = my_abs(x - vv[0].x);
  new_x = vv[0].x;
  new_y = vv[0].y;
  for (int i = 1; i < vv_len; i++)
    if (my_abs(x - vv[i].x) < mn_dist) {
      mn_dist = min(mn_dist, my_abs(x - vv[i].x));
      new_x = vv[i].x;
      new_y = vv[i].y;
    }
  return 1;
}
int sign(long long x) {
  if (x < 0) return -1;
  return 1;
}
long long diag_cover(long long n, long long x1, long long y1, long long x2,
                     long long y2, long long dx, long long dy) {
  if (x1 != x2 && sign(x2 - x1) != sign(dx)) return 0;
  if (y1 != y2 && sign(y2 - y1) != sign(dy)) return 0;
  long long x1_new, y1_new, x2_new, y2_new;
  if (!get_near(n, x1, y1, dx, dy, x1_new, y1_new)) return 0;
  if (!get_near(n, x2, y2, -dx, -dy, x2_new, y2_new)) return 0;
  return my_abs(x1_new - x2_new) + 1;
}
long long solve(long long n, long long x, long long y, long long c) {
  long long cnt = 1;
  long long x_min = x, x_max = x, y_min = y, y_max = y;
  long long tm = 0;
  while (cnt < c) {
    tm++;
    {
      long long x1 = x_min - 1;
      long long y1 = y;
      long long x2 = x;
      long long y2 = y_min - 1;
      cnt += diag_cover(n, x1, y1, x2, y2, +1, -1);
    }
    {
      long long x1 = x_min - 1;
      long long y1 = y;
      long long x2 = x;
      long long y2 = y_max + 1;
      x1++;
      y1++;
      x2--;
      y2--;
      cnt += diag_cover(n, x1, y1, x2, y2, +1, +1);
    }
    {
      long long x1 = x_max + 1;
      long long y1 = y;
      long long x2 = x;
      long long y2 = y_min - 1;
      x1--;
      y1--;
      x2++;
      y2++;
      cnt += diag_cover(n, x1, y1, x2, y2, -1, -1);
    }
    {
      long long x1 = x_max + 1;
      long long y1 = y;
      long long x2 = x;
      long long y2 = y_max + 1;
      cnt += diag_cover(n, x1, y1, x2, y2, -1, +1);
    }
    x_min--;
    x_max++;
    y_min--;
    y_max++;
  }
  return tm;
}
int const MX = 100;
int const dx[4] = {-1, 1, 0, 0};
int const dy[4] = {0, 0, -1, 1};
int solve_slow(int n, int x, int y, int c) {
  int nnew[MX][MX];
  int dst[MX * MX], och_x[MX * MX], och_y[MX * MX];
  for (int i = 0; i < MX; i++)
    for (int j = 0; j < MX; j++) nnew[i][j] = 0;
  nnew[x][y] = 1;
  int p_read = 0, p_write = 1;
  och_x[0] = x;
  och_y[0] = y;
  dst[0] = 0;
  while (p_read < p_write) {
    if (p_write >= c) return dst[p_read];
    int new_p_write = p_write;
    for (int i = p_read; i < p_write; i++) {
      int x = och_x[i];
      int y = och_y[i];
      for (int k = 0; k < 4; k++) {
        int new_x = x + dx[k];
        int new_y = y + dy[k];
        if (new_x >= 1 && new_x <= n && new_y >= 1 && new_y <= n &&
            !nnew[new_x][new_y]) {
          nnew[new_x][new_y] = 1;
          och_x[new_p_write] = new_x;
          och_y[new_p_write] = new_y;
          dst[new_p_write] = dst[p_read] + 1;
          new_p_write++;
        }
      }
    }
    p_read = p_write;
    p_write = new_p_write;
  }
  return -1;
}
int main() {
  long long n, x, y, c;
  cin >> n >> x >> y >> c;
  cout << solve(n, x, y, c);
  return 0;
}

### Prompt

Create a solution in CPP for 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;
struct point {
  long long x, y;
};
long long my_abs(long long x) {
  if (x < 0) return -x;
  return x;
}
int inters_vert(long long n, long long x, long long y, long long dx,
                long long dy, long long X_VAL, point &p) {
  if ((x > X_VAL && dx < 0) || (x < X_VAL && dx > 0)) {
    long long diff = X_VAL - x;
    if (diff < 0) diff = -diff;
    long long new_y = y + diff * dy;
    if (new_y >= 1 && new_y <= n) {
      p.x = X_VAL;
      p.y = new_y;
      return 1;
    } else
      return 0;
  }
  return 0;
}
int inters_hor(long long n, long long x, long long y, long long dx,
               long long dy, long long Y_VAL, point &p) {
  if ((y > Y_VAL && dy < 0) || (y < Y_VAL && dy > 0)) {
    long long diff = Y_VAL - y;
    if (diff < 0) diff = -diff;
    long long new_x = x + diff * dx;
    if (new_x >= 1 && new_x <= n) {
      p.x = new_x;
      p.y = Y_VAL;
      return 1;
    } else
      return 0;
  }
  return 0;
}
int get_near(long long n, long long x, long long y, long long dx, long long dy,
             long long &new_x, long long &new_y) {
  if (x >= 1 && x <= n && y >= 1 && y <= n) {
    new_x = x;
    new_y = y;
    return 1;
  }
  point vv[4], pp;
  int vv_len = 0;
  if (inters_vert(n, x, y, dx, dy, 1, pp)) vv[vv_len++] = pp;
  if (inters_vert(n, x, y, dx, dy, n, pp)) vv[vv_len++] = pp;
  if (inters_hor(n, x, y, dx, dy, 1, pp)) vv[vv_len++] = pp;
  if (inters_hor(n, x, y, dx, dy, n, pp)) vv[vv_len++] = pp;
  if (vv_len == 0) return 0;
  long long mn_dist = my_abs(x - vv[0].x);
  new_x = vv[0].x;
  new_y = vv[0].y;
  for (int i = 1; i < vv_len; i++)
    if (my_abs(x - vv[i].x) < mn_dist) {
      mn_dist = min(mn_dist, my_abs(x - vv[i].x));
      new_x = vv[i].x;
      new_y = vv[i].y;
    }
  return 1;
}
int sign(long long x) {
  if (x < 0) return -1;
  return 1;
}
long long diag_cover(long long n, long long x1, long long y1, long long x2,
                     long long y2, long long dx, long long dy) {
  if (x1 != x2 && sign(x2 - x1) != sign(dx)) return 0;
  if (y1 != y2 && sign(y2 - y1) != sign(dy)) return 0;
  long long x1_new, y1_new, x2_new, y2_new;
  if (!get_near(n, x1, y1, dx, dy, x1_new, y1_new)) return 0;
  if (!get_near(n, x2, y2, -dx, -dy, x2_new, y2_new)) return 0;
  return my_abs(x1_new - x2_new) + 1;
}
long long solve(long long n, long long x, long long y, long long c) {
  long long cnt = 1;
  long long x_min = x, x_max = x, y_min = y, y_max = y;
  long long tm = 0;
  while (cnt < c) {
    tm++;
    {
      long long x1 = x_min - 1;
      long long y1 = y;
      long long x2 = x;
      long long y2 = y_min - 1;
      cnt += diag_cover(n, x1, y1, x2, y2, +1, -1);
    }
    {
      long long x1 = x_min - 1;
      long long y1 = y;
      long long x2 = x;
      long long y2 = y_max + 1;
      x1++;
      y1++;
      x2--;
      y2--;
      cnt += diag_cover(n, x1, y1, x2, y2, +1, +1);
    }
    {
      long long x1 = x_max + 1;
      long long y1 = y;
      long long x2 = x;
      long long y2 = y_min - 1;
      x1--;
      y1--;
      x2++;
      y2++;
      cnt += diag_cover(n, x1, y1, x2, y2, -1, -1);
    }
    {
      long long x1 = x_max + 1;
      long long y1 = y;
      long long x2 = x;
      long long y2 = y_max + 1;
      cnt += diag_cover(n, x1, y1, x2, y2, -1, +1);
    }
    x_min--;
    x_max++;
    y_min--;
    y_max++;
  }
  return tm;
}
int const MX = 100;
int const dx[4] = {-1, 1, 0, 0};
int const dy[4] = {0, 0, -1, 1};
int solve_slow(int n, int x, int y, int c) {
  int nnew[MX][MX];
  int dst[MX * MX], och_x[MX * MX], och_y[MX * MX];
  for (int i = 0; i < MX; i++)
    for (int j = 0; j < MX; j++) nnew[i][j] = 0;
  nnew[x][y] = 1;
  int p_read = 0, p_write = 1;
  och_x[0] = x;
  och_y[0] = y;
  dst[0] = 0;
  while (p_read < p_write) {
    if (p_write >= c) return dst[p_read];
    int new_p_write = p_write;
    for (int i = p_read; i < p_write; i++) {
      int x = och_x[i];
      int y = och_y[i];
      for (int k = 0; k < 4; k++) {
        int new_x = x + dx[k];
        int new_y = y + dy[k];
        if (new_x >= 1 && new_x <= n && new_y >= 1 && new_y <= n &&
            !nnew[new_x][new_y]) {
          nnew[new_x][new_y] = 1;
          och_x[new_p_write] = new_x;
          och_y[new_p_write] = new_y;
          dst[new_p_write] = dst[p_read] + 1;
          new_p_write++;
        }
      }
    }
    p_read = p_write;
    p_write = new_p_write;
  }
  return -1;
}
int main() {
  long long n, x, y, c;
  cin >> n >> x >> y >> c;
  cout << solve(n, x, y, c);
  return 0;
}

```