Задача Субботние дни рождения

Описание

Студент УСД, Герман сидя в кантине и поедая свой очередной ужин вспомнил, что у него недавно был день рождения и о том, что он родился именно в субботу. Хотя в этот раз 17 февраля было среда. Ему стало интересно, сколько его дней рождений было в субботу и когда будет следующие субботнее день рождение. Пока Герман доедал ужин он придумал решение, но для того чтобы проверить его наверняка он решил почитать на wiki про високосные года. Вот что он вычитал:

Продолжительность тропического года (время между двумя весенними равноденствиями) составляет 365 суток 5 часов 48 минут 46 секунд. Различие в продолжительности тропического года и среднего юлианского календарного года (365,25 суток) составляет 11 минут 14 секунд. Из этих 11 минут и 14 секунд приблизительно за 128 лет складываются одни сутки.

По истечении столетий было замечено смещение дня весеннего равноденствия, с которым связаны церковные праздники. К XVI веку весеннее равноденствие наступало примерно на 10 суток раньше 21 марта, используемого для определения дня Пасхи.

Чтобы компенсировать накопившуюся ошибку и избежать подобного смещения в будущем, в 1582 году римский папа Григорий XIII провёл реформу календаря. Чтобы средний календарный год лучше соответствовал солнечному, было решено изменить правило високосных лет. По-прежнему високосным оставался год, номер которого кратен четырём, но исключение делалось для тех, которые были кратны 100. Отныне такие годы были високосными только тогда, когда делились ещё и на 400.

Иными словами, год является високосным, если он кратен 4 и при этом не кратен 100, либо кратен 400. Год не является високосным, если он не кратен 4, либо кратен 100 и не кратен 400.

Годы смены столетий, оканчивающиеся на два нуля, в трёх случаях из четырёх не являются високосными. Так, годы 1700, 1800 и 1900 не были високосными, так как они кратны 100 и не кратны 400. Год 2000 — високосный, так как он кратен 400. 2100, 2200 и 2300 — не високосные. В високосные годы вводится дополнительный день — 29 февраля.

Теперь Герман написав свою программу хочет убедится, что она правильная. Однако Он не стал тратить время на написание проверочной программы, а решил дождаться SDU OPEN и свериться с решениями участников соревнования.

Дана дата рождения, требуется найти год k-того по счету "субботнего" дня рождения. "субботним" днем рождения назовем день рождения которое происходит в тот же день недели что и первое.

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

Во входном файле задано четыре целых числа day, month, year, k (0 < year <= 10^6, 1 <= month <= 12, 1 <= day <= 31, 1 <= k <= 10^3). year, month, day соответствуют дате рождения, k - номер "субботнего" дня рождения.

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

В выходной файл требуется вывести одно число год k-того по счету "субботнего" дня рождения.