Общегородская тренировка 24 июня 2018 года

Соревнование завершилось 24.06.18 в 15:10

A. Latergram

Ограничение по времени: 2 с.
Ограничение по памяти: 256 МБ

Фотограф Иван размещает свои работы в социальной сети Latergram. Приложение Latergram умеет отображать не только каждую фотографию в отдельности, но и “ленту” из миниатюр фотографий. Лента состоит из рядов по m миниатюр.

При загрузке новой фотографии, её миниатюра занимает самое левое место в самом верхнем ряду ленты, при этом остальные миниатюры в первом ряду съезжают на одну позицию вправо, а последняя из них переходит в следующий ряд, куда она добавляется по тем же правилам:

image

Чтобы повысить интерес подписчиков к своей ленте, Иван проделал следующее: он загружал фотографии таким образом, что первые c миниатюр в первых r строках образуют единую картину.

Выглядит это очень здорово, но теперь у Ивана возникла проблема: при загрузке определённого числа новых фотографий, картина может не отображаться в задуманном виде:

image

Иван только что отснял новый сет из n фотографий. Какое максимальное количество из этих фотографий он может загрузить, если хочет, чтобы после этого картина отображалась в ленте правильно?

Входные данные

Первая строка входных данных содержит одно целое число m — количество миниатюр в одном ряду ленты Latergram (1 \leqslant m \leqslant 1000).

Вторая строка содержит два целых числа c и r — количество столбцов и строк в картине, образованной верхними левыми миниатюрами, соответственно (1 \leqslant c \leqslant m, 1 \leqslant r \leqslant 1000).

Третья строка содержит одно целое число n — количество фотографий в новом сете Ивана (1 \leqslant n \leqslant 10^9).

Выходные данные

Вывести одно целое число — максимальное количество фотографий, которое может загрузить Иван.

Примеры
Стандартный вводСтандартный вывод
5
3 4
3
2
5
3 4
6
6