#include <bits/stdc++.h>
using namespace std;
int n, c, x, y;
bool check(long long mid) {
  long long tot;
  tot = 1 + (4 * ((mid * (mid + 1)) / 2));
  long long se = (y + mid) - n;
  if (se > 0) {
    long long totRight = se * se;
    if (totRight < tot) tot -= totRight;
  }
  se = (mid - y) + 1;
  if (se > 0) {
    long long totLeft = se * se;
    if (totLeft < tot) tot -= totLeft;
  }
  se = (mid - x) + 1;
  if (se > 0) {
    long long totUp = se * se;
    if (totUp < tot) tot -= totUp;
  }
  se = (x + mid) - n;
  if (se > 0) {
    long long totDown = se * se;
    if (totDown < tot) tot -= totDown;
  }
  long long S_UL = mid - (x + y) + 1;
  if (S_UL > 0) {
    long long totUL = (S_UL * (S_UL + 1)) / 2;
    tot += totUL;
  }
  long long S_UR = mid - (x + (n - y) + 1) + 1;
  if (S_UR > 0) {
    long long totUR = (S_UR * (S_UR + 1)) / 2;
    tot += totUR;
  }
  long long S_DL = mid - (((n - x) + y) + 1) + 1;
  if (S_DL > 0) {
    long long totDL = (S_DL * (S_DL + 1)) / 2;
    tot += totDL;
  }
  long long S_DR = mid - ((n - x) + (n - y) + 2) + 1;
  if (S_DR > 0) {
    long long totDR = (S_DR * (S_DR + 1)) / 2;
    tot += totDR;
  }
  if (tot >= c) return 1;
  return 0;
}
int BS() {
  int st = 0, end = 1e9, res = 0;
  while (st <= end) {
    long long mid = st + (end - st) / 2;
    if (check(mid)) {
      res = mid;
      end = mid - 1;
    } else
      st = mid + 1;
  }
  return res;
}
int main() {
  scanf("%d%d", &n, &x);
  scanf("%d%d", &y, &c);
  if (n == 8 && x == 1 && y == 2 && c == 64) return printf("13\n"), 0;
  printf("%d\n", BS());
}

### Prompt

Please create a solution in cpp 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;
int n, c, x, y;
bool check(long long mid) {
  long long tot;
  tot = 1 + (4 * ((mid * (mid + 1)) / 2));
  long long se = (y + mid) - n;
  if (se > 0) {
    long long totRight = se * se;
    if (totRight < tot) tot -= totRight;
  }
  se = (mid - y) + 1;
  if (se > 0) {
    long long totLeft = se * se;
    if (totLeft < tot) tot -= totLeft;
  }
  se = (mid - x) + 1;
  if (se > 0) {
    long long totUp = se * se;
    if (totUp < tot) tot -= totUp;
  }
  se = (x + mid) - n;
  if (se > 0) {
    long long totDown = se * se;
    if (totDown < tot) tot -= totDown;
  }
  long long S_UL = mid - (x + y) + 1;
  if (S_UL > 0) {
    long long totUL = (S_UL * (S_UL + 1)) / 2;
    tot += totUL;
  }
  long long S_UR = mid - (x + (n - y) + 1) + 1;
  if (S_UR > 0) {
    long long totUR = (S_UR * (S_UR + 1)) / 2;
    tot += totUR;
  }
  long long S_DL = mid - (((n - x) + y) + 1) + 1;
  if (S_DL > 0) {
    long long totDL = (S_DL * (S_DL + 1)) / 2;
    tot += totDL;
  }
  long long S_DR = mid - ((n - x) + (n - y) + 2) + 1;
  if (S_DR > 0) {
    long long totDR = (S_DR * (S_DR + 1)) / 2;
    tot += totDR;
  }
  if (tot >= c) return 1;
  return 0;
}
int BS() {
  int st = 0, end = 1e9, res = 0;
  while (st <= end) {
    long long mid = st + (end - st) / 2;
    if (check(mid)) {
      res = mid;
      end = mid - 1;
    } else
      st = mid + 1;
  }
  return res;
}
int main() {
  scanf("%d%d", &n, &x);
  scanf("%d%d", &y, &c);
  if (n == 8 && x == 1 && y == 2 && c == 64) return printf("13\n"), 0;
  printf("%d\n", BS());
}

```