Задача C. Биологическая опасность ≡

Условие

Биологическая лаборатория корпорации Umbrella занимает n-этажное здание, на каждом этаже которого расположено по n комнат-отделов. В первой комнате каждого этажа расположена шахта лифта, позволяющего перемещаться между этажами здания.

Однажды на этаже f в комнате r произошел досадный казус, в результате которого на свободу вырвался опасный T-вирус. За одну минуту он заражает соседнюю комнату, если она граничит с уже зараженной. На другие этажи вирус может проникнуть только через шахту лифта с той же скоростью. За пределы здания вирус распространиться не может.

Определите количество зараженных отделов лаборатории через t минут после инцидента.

Формат входных данных

Четыре строки входных данных содержат четыре натуральных числа: n, f, r и t.

Формат выходных данных

Выведите одно натуральное число — ответ на вопрос задачи.

Ограничения

1 ≤ f, r ≤ n ≤ 10⁹

1 ≤ t ≤ 10⁹

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n ≤ 100, получат не менее 60 баллов.

Пояснение к примеру

Смотри рисунок.

Примеры тестов

10
7
3
7

28