D. Ноён Бэндэр ба квадрат

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Ноён Бэндэрт $n × n$ харьцаатай электрон хүснэгт байна. Энэ хүснэгтийн нүд болгон асаалттай эсвэл унтарсан байж болдог. Хэрвээ хүснэгтийн дор хаяж $c$ ширхэг нүд асвал Ноён Бэндэр баярлах болно.

Хүснэгт дээрээс доош $1$-ээс $n$ хүртэл, зүүнээс баруун уруу $1$-ээс $n$ хүртэл дугаарлагджээ. Анх хүснэгтэд $(x, y)$ ($x$ нь мөрийн дугаар, $y$ нь баганын дугаар) координаттай нэг ширхэг нүд асаалттай байна. Харин бусад бүх нүднүүд унтраалттай. Секунд болгонд асаалттай нүдний зэргэлдээ нүдийг асаах боломжтой.

$(x, y)$ координаттай нүдний зэргэлдээ нүд гэдэг нь $(x - 1, y)$, $(x + 1, y)$, $(x, y - 1)$, $(x, y + 1)$ координаттай нүднүүд юм.

Хамгийн хурданаар хэдэн секундэд Ноён Бэндэрийг баярлуулж болохоор байна вэ?

Оролт

Оролтонд зайгаар тусгаарлагдсан бүхэл тоонууд $n, x, y, c$ $(1 ≤ n, c ≤ 10^{9}; 1 ≤ x, y ≤ n; c ≤ n^{2})$ өгөгдөнө.

Гаралт

Бодлогын хариу болох нэг бүхэл тоог хэвлэнэ үү.

Орчуулсан: Энхлут

Жишээ тэстүүд

Оролт
6 4 3 1
Гаралт
0
Оролт
9 3 8 10
Гаралт
2

Тэмдэглэл

Эхний жишээнд анх нэг ширхэг нүд асаалттай байна. Тиймээс хариу нь $0$.

Хоёр дахь жишээнд дараах байдлаар асах үйл явц явагдана.

.

Сэтгэгдлүүдийг ачааллаж байна...