#include <bits/stdc++.h>
using namespace std;
long long size_length, x, y, needed_on;
map<char, long long> compass;
bool ok(long long mid);
void get_vec_input(vector<long long>& vec, long long n) {
  vec.reserve(n);
  for (size_t i = 0; i < n; i++) {
    long long temp;
    cin >> temp;
    vec.push_back(temp);
  }
}
void print_vec(vector<long long>& vec, string sign) {
  for (auto&& elem : vec) {
    cout << elem << sign;
  }
  cout << endl;
}
long long max_binary_search(long long start_value, long long end_value) {
  long long start = start_value, end = end_value;
  while (start < end) {
    long long mid = start + ((end - start + 1) / 2);
    if (ok(mid)) {
      start = mid;
    } else {
      end = mid - 1;
    }
  }
  return start;
}
long long min_binary_search(long long start_value, long long end_value) {
  long long start = start_value, end = end_value;
  while (start < end) {
    long long mid = start + ((end - start) / 2);
    if (ok(mid)) {
      end = mid;
    } else {
      start = mid + 1;
    }
  }
  return start;
}
long long compute_area(long long mid, long long x_axis, long long y_axis) {
  if (x_axis + y_axis <= mid) {
    return (x_axis * y_axis);
  }
  long long result = ((mid - 1) * (mid - 1 + 1)) / 2;
  if (x_axis < mid) {
    result -= ((mid - 1 - x_axis) * (mid - 1 - x_axis + 1)) / 2;
  }
  if (y_axis < mid) {
    result -= ((mid - 1 - y_axis) * (mid - 1 - y_axis + 1)) / 2;
  }
  return result;
}
bool ok(long long mid) {
  long long up_right_on = compute_area(mid, compass['E'], compass['N']);
  long long up_left_on = compute_area(mid, compass['W'], compass['N']);
  long long down_right_on = compute_area(mid, compass['E'], compass['S']);
  long long down_left_on = compute_area(mid, compass['W'], compass['S']);
  long long postive_y_axis = (compass['N'] > mid) ? mid : compass['N'];
  long long neg_y_axis = (compass['S'] > mid) ? mid : compass['S'];
  long long postive_x_axis = (compass['E'] > mid) ? mid : compass['E'];
  long long neg_x_axis = (compass['W'] > mid) ? mid : compass['W'];
  long long current_on =
      (up_right_on + up_left_on + down_right_on + down_left_on) +
      (postive_x_axis + neg_x_axis + postive_y_axis + neg_y_axis) + 1;
  return (current_on >= needed_on);
}
bool comparison(pair<long long, long long> p1, pair<long long, long long> p2) {
  if (p1.second < p2.second) return true;
  if (p1.second > p2.second) return false;
  return p1.first <= p2.first;
};
int main(int argc, char const* argv[]) {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> size_length >> x >> y >> needed_on;
  compass['N'] = x - 1;
  compass['W'] = y - 1;
  compass['S'] = size_length - x;
  compass['E'] = size_length - y;
  long long result;
  if (needed_on == 1) {
    result = 0;
  } else {
    result = min_binary_search(0, 1e10 + 10);
  }
  cout << result << endl;
  return 0;
}

### Prompt

Your task is to create 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 size_length, x, y, needed_on;
map<char, long long> compass;
bool ok(long long mid);
void get_vec_input(vector<long long>& vec, long long n) {
  vec.reserve(n);
  for (size_t i = 0; i < n; i++) {
    long long temp;
    cin >> temp;
    vec.push_back(temp);
  }
}
void print_vec(vector<long long>& vec, string sign) {
  for (auto&& elem : vec) {
    cout << elem << sign;
  }
  cout << endl;
}
long long max_binary_search(long long start_value, long long end_value) {
  long long start = start_value, end = end_value;
  while (start < end) {
    long long mid = start + ((end - start + 1) / 2);
    if (ok(mid)) {
      start = mid;
    } else {
      end = mid - 1;
    }
  }
  return start;
}
long long min_binary_search(long long start_value, long long end_value) {
  long long start = start_value, end = end_value;
  while (start < end) {
    long long mid = start + ((end - start) / 2);
    if (ok(mid)) {
      end = mid;
    } else {
      start = mid + 1;
    }
  }
  return start;
}
long long compute_area(long long mid, long long x_axis, long long y_axis) {
  if (x_axis + y_axis <= mid) {
    return (x_axis * y_axis);
  }
  long long result = ((mid - 1) * (mid - 1 + 1)) / 2;
  if (x_axis < mid) {
    result -= ((mid - 1 - x_axis) * (mid - 1 - x_axis + 1)) / 2;
  }
  if (y_axis < mid) {
    result -= ((mid - 1 - y_axis) * (mid - 1 - y_axis + 1)) / 2;
  }
  return result;
}
bool ok(long long mid) {
  long long up_right_on = compute_area(mid, compass['E'], compass['N']);
  long long up_left_on = compute_area(mid, compass['W'], compass['N']);
  long long down_right_on = compute_area(mid, compass['E'], compass['S']);
  long long down_left_on = compute_area(mid, compass['W'], compass['S']);
  long long postive_y_axis = (compass['N'] > mid) ? mid : compass['N'];
  long long neg_y_axis = (compass['S'] > mid) ? mid : compass['S'];
  long long postive_x_axis = (compass['E'] > mid) ? mid : compass['E'];
  long long neg_x_axis = (compass['W'] > mid) ? mid : compass['W'];
  long long current_on =
      (up_right_on + up_left_on + down_right_on + down_left_on) +
      (postive_x_axis + neg_x_axis + postive_y_axis + neg_y_axis) + 1;
  return (current_on >= needed_on);
}
bool comparison(pair<long long, long long> p1, pair<long long, long long> p2) {
  if (p1.second < p2.second) return true;
  if (p1.second > p2.second) return false;
  return p1.first <= p2.first;
};
int main(int argc, char const* argv[]) {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> size_length >> x >> y >> needed_on;
  compass['N'] = x - 1;
  compass['W'] = y - 1;
  compass['S'] = size_length - x;
  compass['E'] = size_length - y;
  long long result;
  if (needed_on == 1) {
    result = 0;
  } else {
    result = min_binary_search(0, 1e10 + 10);
  }
  cout << result << endl;
  return 0;
}

```