Дистанционный практикум по программированию

В некоторой школе учатся N детей. Директору школы стало интересно, когда наступит ближайшая дата, что сумма всех возрастов данных учеников станет больше или равна K.

Заметим, что под словом "возраст" директор понимает целое число − количество полных лет. Например, если ученик родился 15.11.2000, то 14.11.2016 ему ещё 15 лет, а 15.11.2016 − уже 16.

Также директор считает, что если ученик родился 29 февраля, то в невисокосные годы его день рождения следует отмечать 1 марта, а вовсе не 28 февраля.

Напишите программу, которая поможет директору найти искомую дату.

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

В первой строке через пробел записаны два целых числа N и K.

В следующих N строках записаны даты рождения в формате ДД.ММ.ГГГГ (первые две цифры − номер дня в месяце, затем идёт точка, следующие две цифры − номер месяца, далее снова точка, последние четыре цифры − год).

Ограничения: 1 ≤ N ≤ 10⁵,  20∙N ≤ K ≤ 1000∙N, все даты лежат в интервале от 01.01.1998 до 31.12.2010 включительно.

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

Искомая дата в формате ДД.ММ.ГГГГ

Пример ввода 2 40 06.03.2000 27.05.2001 Пример вывода 06.03.2021

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

Система оценивания.

Подзадача 1 (до 50 баллов): 1 ≤ N ≤ 100

Подзадача 2 (до 50 баллов): 1 ≤ N ≤ 10⁵