Задача №114147. Расписание
Как же Илье надоело учиться! Сначала школа, потом университет... Вот, наконец, наступил тот долгожданный день, когда Илье утром не надо ехать на учебу. Но, к несчастью для Ильи, оказалось, что после окончания университета начинается самое трудное — надо устраиваться на работу.
Во всемирно известной фирме «Goondex», в которую устроился Илья, принято очень много работать, в частности, для сотрудников установлена шестидневная рабочая неделя. Но, в качестве бонуса, «Goondex» каждый год предлагает своим сотрудникам выбрать любой день недели в качестве выходного. В свою очередь, оставшиеся шесть дней недели будут рабочими.
Илья сообразил, что с учётом государственных праздников (которые всегда являются выходными) с помощью правильного выбора выходного дня недели можно варьировать количество рабочих дней в году. Теперь он хочет знать, какой день недели ему следует выбрать в качестве выходного, чтобы отдыхать как можно больше дней в году, или, наоборот, демонстрировать чудеса трудолюбия, работая по максимуму.
В первой строке входных данных находится одно целое число N ( 0 ≤ N ≤ 366 ) — количество государственных праздников.
Во второй строке содержится одно целое число year ( 1800 ≤ year ≤ 2100 ) — год, в который необходимо помочь Илье.
В каждой из последующих N строк расположено по паре чисел day month ( day — целое число, month — слово, между day и month ровно один пробел), обозначающих, что день day месяца month является государственным праздником.
В последней строке расположено слово day _ of _ week — день недели первого января в год year .
Гарантируется, что все даты указаны корректно (в том числе указанный день недели первого января действительно является днём недели первого января соответствующего года year ) и все дни государственных праздников различны.
Выведите через пробел два дня недели — лучший и худший варианты дней недели для выходного (то есть дни недели, для которых достигается соответственно максимальное и минимальное количество выходных дней в году). Если возможных вариантов ответа несколько, выведите любой из них.
Тесты к этой задаче состоят из трёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
2 2015 1 January 8 January Thursday
Monday Thursday
3 2013 1 January 8 January 15 January Tuesday
Monday Tuesday
3 2013 6 February 13 February 20 February Tuesday
Tuesday Wednesday