Осень — время, когда часто отключают горячую воду. Впрочем, дома у Кеши имеется водонагреватель накопительного типа, так что по поводу отключений он переживает не очень сильно.
Включив водонагреватель, Кеша считает правильным дождаться его полного нагрева. Для этого требуется $$$k$$$ минут, при этом каждую минуту водонагреватель потребляет $$$w$$$ ватт.
Дома у Кеши установлен двухфазный счетчик электроэнергии. Согласно тарифам, начиная с момента времени $$$h_1$$$ часов $$$m_1$$$ минут и до момента времени $$$h_2$$$ часов $$$m_2$$$ минут, электроэнергия обходится в $$$p$$$ копеек за ватт, а в остальное время — в $$$q$$$ копеек за ватт.
Кеша включил водонагреватель в момент времени $$$s$$$ часов $$$u$$$ минут. Ваша задача — определить, сколько (в копейках) будет стоить полный нагрев.
В первой строке содержится целое число $$$k$$$ $$$(1 \le k \le 10^6)$$$ — время (в минутах), необходимое для полного нагрева водонагревателя.
Во второй строке содержится целое число $$$w$$$ $$$(1 \le w \le 10^6)$$$ — количество ватт, потребляемое водонагревателем в минуту.
В третьей строке содержится целое число $$$p$$$ $$$(1 \le p \le 10^6)$$$ — стоимость ватта согласно первому тарифу.
В четвёртой строке содержится целое число $$$q$$$ $$$(1 \le q \le 10^6)$$$ — стоимость ватта согласно второму тарифу.
В пятой строке содержится целое число $$$h_1$$$ $$$(0 \le h_1 \le 23)$$$, а в шестой строке содержится целое число $$$m_1$$$ $$$(0 \le m_1 \le 59)$$$ — час и минута, в которые начинает действовать тариф в $$$p$$$ копеек за ватт.
В седьмой строке содержится целое число $$$h_2$$$ $$$(0 \le h_2 \le 23)$$$, а в восьмой строке содержится целое число $$$m_2$$$ $$$(0 \le m_2 \le 59)$$$ — час и минута, в которые начинает действовать тариф в $$$q$$$ копеек за ватт.
В девятой строке содержится целое число $$$s$$$ $$$(0 \le s \le 23)$$$, а в десятой строке содержится целое число $$$u$$$ $$$(0 \le u \le 59)$$$ — час и минута, в которые Кеша включает водонагреватель.
Выведите единственное целое число — сумму (в копейках), в которую обойдется полный нагрев водонагревателя.
Во всех подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов.
Для всех подзадач, кроме первой, требуется, чтобы программа верно решала одну или несколько из предшествующих подзадач. Более подробно разбиение на подзадачи показано в таблице ниже.
| Подзадача | Баллы за тест | Ограничения | Необходимые | Информация | |
| (баллы | подзадачи | о проверке | |||
| за подзадачу) | |||||
| 1 | 1 (до 10) | $$$m_1 = m_2 = u = 0$$$, $$$h_1 | lt; h_2$$$, | нет | полная |
| $$$1 \le k, \, w, \, p, \, q \le 10^3$$$ | |||||
| гарантируется, что водонагреватель | |||||
| полностью нагреется до истечения | |||||
| текущих суток | |||||
| 2 | 1 (до 10) | $$$m_1 = m_2 = u = 0$$$ | 1 | полная | |
| $$$1 \le k, \, w, \, p, \, q \le 10^3$$$ | |||||
| 3 | 1 (до 10) | $$$h_1 | lt; h_2$$$, | 1 | полная |
| $$$1 \le k, \, w, \, p, \, q \le 10^3$$$ | |||||
| гарантируется, что водонагреватель | |||||
| полностью нагреется до истечения | |||||
| текущих суток | |||||
| 4 | 2 (до 40) | $$$1 \le k, \, w, \, p, \, q \le 10^3$$$ | 2, 3 | полная | |
| 5 | 1 (до 30) | любые возможные значения | 4 | полная |
10 2 3 4 12 13 14 15 12 10
66
200 30 250 508 23 30 1 20 22 35
2196600
Поясним приведённые примеры.
В первом примере стоимость ватта составляет $$$3$$$ копейки с момента $$$12:13$$$ до момента $$$14:15$$$. В остальное время стоимость ватта составляет $$$4$$$ копейки. Кеша включает водонагреватель в $$$12:10$$$, полный нагрев произойдёт за $$$10$$$ минут. Каждую минуту водонагреватель потребляет $$$2$$$ ватта. Следовательно, до момента $$$12:13$$$, пока водонагреватель будет работать по второму тарифу, на нагрев воды будет израсходовано $$$2 \cdot 3 \cdot 4 = 24$$$ копейки. Следующие $$$7$$$ минут водонагреватель будет работать по первому тарифу, так что на нагрев воды будет израсходовано $$$2 \cdot 7 \cdot 3 = 42$$$ копейки. Суммарно получаем $$$66$$$ копеек.
Во втором примере стоимость ватта составляет $$$250$$$ копеек с $$$23:30$$$ до $$$01:20$$$, в остальное время — $$$508$$$ копеек.
Для полного нагрева водонагреватель должен работать в течение $$$200$$$ минут. Каждую минуту он потребляет $$$30$$$ ватт.
Кеша включает водонагреватель в $$$22:35$$$. В это время и до $$$23:30$$$ действует второй тариф, так что за $$$55$$$ минут (которые пройдут с $$$22:35$$$ до $$$23:30$$$) на нагрев воды будет израсходовано $$$55 \cdot 30 = 1650$$$ ватт, которые обойдутся в $$$1650 \cdot 508 = 838200$$$ копеек.
В течение следующих $$$1$$$ часа $$$50$$$ минут стоимость ватта будет составлять $$$250$$$ копеек, и работа водонагревателя обойдётся в $$$(60 + 50) \cdot 30 \cdot 250 = 825000$$$ копеек.
До полного нагрева водонагревателю потребуется проработать ещё $$$200 - 55 - 110 = 35$$$ минут, которые придётся оплатить по второму тарифу. Необходимая сумма составит $$$35 \cdot 30 \cdot 508 = 533400$$$ копеек.
Суммируя, получим $$$838200 + 825000 + 533400 = 2196600$$$ копеек.
Кеша часто гуляет вместе со своим другом Мелентием. Обычно ребята сначала делают домашнее задание, а потом уже отправляются на прогулку.
Сегодня им на дом задали $$$n$$$ примеров. Впрочем, друзья полагают, что все примеры решать не обязательно. Кеша считает, что вполне достаточно решить $$$dk$$$ примеров, а Мелентий уверен, что можно ограничиться решением $$$dm$$$ примеров. На решение одного пример Кеша тратит $$$tk$$$ минут, а Мелентий — $$$tm$$$ минут. Решив один пример, каждый из ребят немедленно приступает к решению следующего.
Как только кто-то из ребят решит достаточное (с его точки зрения) количество примеров, сразу же позовёт товарища на прогулку. Если к этому моменту товарищ также решил достаточное количество примеров и не занят решением другого примера, он соглашается, и ребята отправятся гулять. Если же товарищ занят решением примера, он попросит подождать, и тогда пригласивший продолжит решать примеры.
Заканчивая решение очередного примера сверх достаточного количества, каждый из ребят будет обращаться к товарищу с предложением погулять. Товарищ же ответит согласием в том случае, если не занят решением примера в этот момент.
Ваша задача — определить, сколько примеров решит каждый из ребят, прежде чем они отправятся гулять.
В первой строке содержится целое число $$$n$$$ $$$(1 \le n \le 10^{12})$$$ — количество заданных на дом примеров.
Во второй строке содержится целое число $$$dk$$$ $$$(1 \le dk \le n)$$$ — количество примеров, которое считает достаточным решить Кеша.
В третьей строке содержится целое число $$$tk$$$ $$$(1 \le tk \le 10^6)$$$ — количество минут, которое требуется Кеше на решение одного примера.
В четвертой строке содержится целое число $$$dm$$$ $$$(1 \le dm \le n)$$$ — количество примеров, которое считает достаточным решить Мелентий.
В пятой строке содержится целое число $$$tm$$$ $$$(1 \le tm \le 10^6)$$$ — количество минут, которое требуется Мелентию на решение одного примера.
Выведите два целых числа — количество примеров, которое решит Кеша, и количество примеров, которое решит Мелентий. Разделяйте числа переводом строки или пробелом.
Во всех подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов внутри этой подзадачи, которые не были пройдены.
Проверка решения на тестах всех подзадач, кроме первой, осуществляется только, если пройдены все тесты некоторых или всех предшествующих подзадач. Разделение на подзадачи показано в таблице ниже.
| Подзадача | Баллы за тест | Ограничения | Необходимые | Информация |
| (баллы | подзадачи | о проверке | ||
| за подзадачу) | ||||
| 1 | 1 (до 5) | $$$n \le 10$$$, $$$tk = 1$$$, $$$tm \le 10$$$ | нет | полная |
| 2 | 1 (до 5) | $$$n \le 10$$$, $$$tk \le 10$$$, $$$tm \le 10$$$ | 1 | полная |
| 3 | 1 (до 10) | $$$n \le 1000$$$, $$$tk \le 1000$$$, $$$tm \le 1000$$$ | 2 | полная |
| 4 | 2 (до 20) | $$$n \le 10^6$$$, $$$tk \le 10^6$$$, $$$tm \le 10^6$$$ | 3 | полная |
| 5 | 1 (до 5) | $$$n \le 10^{12}$$$, $$$tk = tm \le 10^6$$$ | 1 | полная |
| 6 | 1 (до 5) | $$$n \le 10^{12}$$$, $$$tk = 1$$$, $$$ tm \le 10^6$$$ | 1 | полная |
| 7 | 1 (до 5) | $$$n \le 10^{12}$$$, $$$tk \le 10^6$$$, $$$tm \le 10^6$$$, | 5, 6 | полная |
| $$$tm$$$ делится на $$$tk$$$ нацело (без остатка) | ||||
| 8 | 2 (до 20) | $$$n \le 10^{12}$$$, $$$tk \le 10^6$$$, $$$tm \le 10^6$$$, | 5, 6 | полная |
| $$$tk$$$ и $$$tm$$$ взаимно простые | ||||
| 9 | 0 (25) | $$$n \le 10^{12}$$$, $$$tk \le 10^6$$$, $$$tm \le 10^6$$$ | 4, 7, 8 | полная |
10 5 3 4 4
8 6
100 17 9 23 6
18 27
Поясним приведённые примеры.
В первом примере произойдёт следующее.
Кеша за $$$15$$$ минут решит $$$5$$$ примеров (количество, которое он считает достаточным) и пригласит Мелентия гулять. Однако, к сожалению Кеши, Мелентий ответит отказом, поскольку ещё не решил достаточное (с его точки зрения) количество примеров. Мелентию для этого требуется $$$16$$$ минут.
Кеша приступит к решению следующего, шестого, примера, и вплоть до $$$18$$$ минуты будет занят им. Так что когда Мелентий решит $$$4$$$ примера и обратится к Кеше, Кеша ответит, что хотел бы дорешать пример, который уже начал.
Мелентий, в свою очередь, также станет решать следующий, пятый, пример. В момент времени $$$18$$$ Кеша вновь пригласит Мелентия гулять, но Мелентий опять откажется: до минуты $$$20$$$ включительно он будет решать пример.
Кеша станет решать седьмой пример, решение которого он завершит в минуту $$$21$$$. За минуту до этого Мелентий пригласит его гулять, но Кеша вновь сообщит товарищу, что хочет закончить решение. А в минуту $$$21$$$ занят окажется уже Мелентий — он как раз начнёт решать шестой пример, поэтому Кеша приступит к решению восьмого примера.
Однако по прошествии $$$24$$$ минут ребята отправятся на прогулку: Кеша закончит решать восьмой пример, а Мелентий — шестой.
Во втором примере произойдёт следующее.
Кеша будет решать желаемые $$$17$$$ примеров в течение $$$153$$$ минут, а Мелентий справится со своими $$$23$$$ примерами за $$$138$$$ минут. Так что именно Мелентий начнёт первым интересоваться у Кеши, не пойдёт ли тот гулять.
Пока Кеша будет дорешивать свои примеры, Мелентий успеет решить два дополнительных примера полностью и один — частично. Так что когда Кеша завершит решение $$$17$$$ примера, Мелентий будет занят решением $$$26$$$ примера. Кеше ничего не останется, как начать решать следующий, $$$18$$$ пример.
В минуту $$$156$$$ Мелентий завершит решение $$$26$$$ примера и поинтересуется у Кеши, не готов ли он погулять. Получив отрицательный ответ, он примется решать $$$27$$$ пример. Этот пример он закончит решать в минуту $$$162$$$. В этот же момент свой $$$18$$$ пример закончит решать и Кеша, после чего ребята отправятся на прогулку.
Кеша любит кататься на роликовых коньках. Он полагает (и в этом с ним согласны большинство роллеров), что кататься по асфальту значительно приятнее, нежели по плитке. Однако, к огорчению роллеров, местные власти постепенно меняют асфальт на плитку.
Один из тротуаров, по которому нравится кататься Кеше, можно описать последовательностью латинских символов $$$A$$$ и $$$T$$$. Символ $$$A$$$ соответствует участку из асфальта единичной длины, а символ $$$T$$$ соответствует участку из плитки единичной длины.
В ближайшее время местные власти планируют заменить асфальт на плитку ровно на двух участках (на большее не хватает финансов). Местные власти справедливо полагают, что чем короче будет непрерывная последовательность асфальтовых участков, тем до меньшей скорости будут разгоняться на этом отрезке тротуара роллеры. Поэтому они хотят выбрать два асфальтовых участка таким образом, чтобы после замены максимальная суммарная длина последовательно расположенных асфальтовых участков на тротуаре была минимально возможной.
Ваша задача — определить номера участков, на которых следует заменить асфальт плиткой, чтобы выполнить требование местных властей, а так же наибольшую длину из расположенных подряд участков с асфальтом после такой замены. Считайте, что участки занумерованы, начиная с $$$1$$$.
В первой строке содержится последовательность латинских символов $$$A$$$ и $$$T$$$, содержащая не менее $$$2$$$ и не более $$$4 \cdot 10^5$$$ символов.
Гарантируется, что в последовательности содержится не менее двух символов $$$A$$$.
Выведите три целых числа — наибольшую длину из расположенных подряд участков с асфальтом после оптимальной замены, а так же номера участков, на которых следует заменить асфальт плиткой. Разделяйте числа пробелом или переводом строки.
Если существует несколько вариантов ответа — выведите любой из вариантов.
Во всех подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов.
Для всех подзадач, кроме первой, требуется, чтобы программа верно решала одну или несколько из предшествующих подзадач. Более подробно разбиение на подзадачи показано в таблице ниже.
| Подзадача | Баллы за тест | Ограничения | Необходимые | Информация |
| (баллы | подзадачи | о проверке | ||
| за подзадачу) | ||||
| 1 | 2 (до 10) | длина строки не превышает $$$10$$$ | нет | полная |
| 2 | 2 (до 10) | длина строки не превышает $$$100$$$ | 1 | полная |
| 3 | 2 (до 20) | длина строки не превышает $$$1000$$$ | 2 | полная |
| 4 | 2 (до 6) | в строке содержатся только символы $$$A$$$ | 2 | полная |
| 5 | 2 (до 6) | все символы $$$A$$$, содержащиеся в строке, | 4 | полная |
| образуют одну непрерывную | ||||
| последовательность | ||||
| 6 | 2 (до 6) | все символы $$$T$$$, содержащиеся в строке, | 4 | полная |
| образуют одну непрерывную | ||||
| последовательность | ||||
| 7 | 2 (до 6) | символы $$$A$$$, содержащиеся в строке, | 3, 5, 6 | полная |
| образуют не более двух | ||||
| непрерывных последовательностей | ||||
| 8 | 2 (до 36) | любые символьные последовательности, | 7 | полная |
| удовлетворяющие условиям задачи |
TTAAATAAAAT
2 8 4
TTTAAAAAAATTTAAAAAATTAAAAAAAT
6 7 25
Поясним приведённые примеры.
В первом примере одной из оптимальных замен является замена асфальта на участках $$$4$$$ и $$$8$$$. После изменений тротуар будет иметь вид $$$TTA[T]ATA[T]AAT$$$ (в скобках указаны участки с заменой). Легко увидеть, что наибольшее количество расположенных подряд участков с асфальтом равно $$$2$$$ (участки $$$9$$$ и $$$10$$$).
Обратим внимание, что в первом примере это не единственная оптимальная замена. Например, замены $$$3$$$ $$$8$$$ привели бы к тротуару $$$TT[T]AATAA[T]AT$$$, в котором наибольшее количество расположенных подряд участков с асфальтом так же равно $$$2$$$ (участки $$$4$$$ и $$$5$$$; $$$7$$$ и $$$8$$$).
Во втором примере после замен $$$7$$$ и $$$25$$$ тротуар примет вид $$$TTTAAA[T]AAATTTAAAAAATTAAA[T]AAAT$$$. Легко увидеть, что наибольшее количество расположенных подряд участков с асфальтом равно $$$6$$$ (участки с $$$14$$$ до $$$19$$$).
Осень — это время для ремонта тепловых сетей. Конечно, их уже ремонтировали летом, но после испытаний на $$$n$$$ участках теплотрассы случились прорывы. Для каждого прорыва $$$\#j$$$ известен день $$$d_j$$$, в который произошёл прорыв. Данные о прорывах упорядочены хронологически.
Чтобы провести ремонт, нужно сначала выкопать котлован. Тогда рабочие получат доступ к трубам и смогут остановить утечку. Однако есть проблема: для рытья котлована необходим экскаватор, и он имеется в распоряжении ремонтной службы — но только один.
Поэтому ремонтные службы действуют следующим образом.
Когда случается прорыв, оформляется заявка на ремонт участка. Заявки упорядочиваются хронологически; если в один день поступает более одной заявки, они упорядочиваются по номерам. По заявке на участок направляется экскаватор, которому требуется $$$k$$$ полных дней на рытьё котлована. Как только котлован будет вырыт, утечка воды будет остановлена.
В день, когда произошёл первый прорыв, экскаватор был свободен и сразу же был отправлен на рытьё котлована согласно первой поступившей заявке. Завершив работу на одном участке, экскаватор может приступить к работе на другом участке уже на следующий день. Разумеется, если имеется заявка с этого другого участка.
Каждый день Кеше приходится идти вдоль этой самой теплотрассы. Когда утечка остановлена, за ночь над котлованом сооружают мостки, и, начиная со следующего дня после завершения рытья котлована, Кеша может идти по мосткам. Но когда прорыв уже случился, а котлован ещё не выкопан, Кеше приходится обходить этот участок.
Ваша задача — определить максимальное количество участков, которые пришлось обходить Кеше в течение одного дня, а также количество дней, в которые Кеше пришлось обходить максимальное количество участков.
В первой строке содержатся целые числа $$$n$$$ и $$$k$$$ $$$(1 \le n \le 3 \cdot 10^5, \, 1 \le k \le 10^9)$$$ — количество прорывов на теплотрассе и количество дней, необходимое для рытья котлована.
Во второй строке содержится $$$n$$$ целых чисел $$$d_1, d_2, \ldots, d_n$$$ $$$(1 \le d_1 \le d_2 \le ... \le d_n \le 10^9)$$$ — дни, в которые случился очередной прорыв.
Выведите два целых числа: максимальное количество участков, которые пришлось обходить Кеше в течение одного дня, и количество дней, в которые Кеше пришлось обходить максимальное количество участков.
В первых семи подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов.
Баллы за восьмую подзадачу начисляются только в случае прохождения всех тестов этой подзадачи. Участнику сообщается либо номер первого непройденного теста и результат проверки на этом тесте, либо что все тесты подзадачи пройдены
Для всех подзадач, кроме первой, требуется, чтобы программа верно решала одну или несколько из предшествующих подзадач. Более подробно разбиение на подзадачи показано в таблице ниже.
| Подзадача | Баллы за тест | Ограничения | Необходимые | Информация |
| (баллы | подзадачи | о проверке | ||
| за подзадачу) | ||||
| 1 | 2 (до 6) | $$$n=2$$$, $$$d[i] \le 100$$$, $$$k \le 100$$$, | нет | полная |
| все $$$d[i]$$$ попарно различны | ||||
| 2 | 2 (до 6) | $$$n \le 10$$$, $$$d[i] \le 100$$$, $$$k \le 100$$$, | 1 | полная |
| все $$$d[i]$$$ попарно различны | ||||
| 3 | 2 (до 10) | $$$n \le 1000$$$, $$$d[i] \le 10^6$$$, $$$k \le 1000$$$, | 2 | полная |
| все $$$d[i]$$$ попарно различны | ||||
| 4 | 2 (до 14) | $$$n \le 1000$$$, $$$d[i] \le 10^6$$$, $$$k \le 1000$$$ | 3 | полная |
| 5 | 2 (до 10) | $$$n \le 1000$$$, $$$d[i] \le 10^9$$$, $$$k \le 10^6$$$ | 4 | полная |
| 6 | 2 (до 6) | $$$n \le 3 \cdot 10^5$$$, $$$d[i] \le 10^9$$$, $$$k = 1$$$ | 1 | полная |
| 7 | 2 (до 6) | $$$n \le 3 \cdot 10^5$$$, $$$d[i] \le 10^9$$$, $$$k = 2$$$ | 1 | полная |
| 8 | 0 (40) | $$$n \le 3 \cdot 10^5$$$, $$$d[i] \le 10^9$$$, $$$k \le 10^9$$$ | 5,6,7 | первая ошибка |
10 11 1 5 8 17 19 28 32 45 51 64
5 10
Поясним приведённый пример.
В день $$$\#1$$$ на одном из участков теплотрассы случается прорыв. В этот же день туда отправляется экскаватор, который проработает там до дня $$$\#11$$$ включительно. В течение всех этих дней Кеше придётся обходить этот участок.
Пока экскаватор копает котлован на первом участке, произойдут прорывы в дни $$$\#5$$$ и $$$\#8$$$. Заявки на ремонт будут ожидать своего исполнения, а Кеше придётся идти в обход: сначала двух, а потом и трёх участков.
Начиная с дня $$$\#12$$$ над первым котлованом будут сооружены мостки, и Кеше не придётся обходить этот участок. Таким образом, количество участков, которые Кеше приходится обходить в течение дня, уменьшится до $$$2$$$. Экскаватор же отправится на рытьё котлована на втором участке (на котором произошёл прорыв в день $$$\#5$$$. На этом участке экскаватор будет работать до дня $$$\#22$$$ включительно.
Однако в день $$$\#17$$$, а затем в день $$$\#19$$$ произойдут прорывы на четвёртом и пятом участках. Это приведёт к возрастанию количества участков, которые Кеша обходит, сначала до $$$3$$$, а затем до $$$4$$$. Уменьшение количества таких участков до $$$3$$$ произойдёт в день $$$\#23$$$, когда экскаватор, завершив работы на втором участке, приедет работать на третий участок (прорыв на котором произошел в день $$$\#8$$$).
Очередной котлован экскаватор будет копать до дня $$$\#33$$$. Но в дни $$$\#28$$$ и $$$\#32$$$ произойдут прорывы на шестом и седьмом участках. Таким образом, в день $$$\#32$$$ количество участков, которые Кеша обходит, впервые станет равным $$$5$$$.
Впрочем, в день $$$\#33$$$ экскаватор завершит работу на третьем участке, и в день $$$\#34$$$ над этим котлованом уже будут проложены мостки, а экскаватор отправится копать четвёртый котлован. Но в дни $$$\#32$$$ и $$$\#33$$$ Кеша будет вынужден обходить пять участков.
Рытьём четвёртого котлована экскаватор будет занят вплоть до конца дня $$$\#44$$$. В день $$$\#45$$$ над четвёртым участком будут положены мостки, экскаватор начнёт работы на пятом участке, но в этот же день случится прорыв на восьмом участке. Так что Кеше по прежнему нужно будет идти в обход четырёх участков. А в день $$$\#51$$$ количество участков, которые нужно обходить, вновь возрастёт до $$$5$$$ из-за прорыва на девятом участке.
До дня $$$\#55$$$ включительно, пока экскаватор работает на пятом участке, Кеша будет вновь вынужден обходить пять участков. Он будет делать это в течение пяти дней (с $$$\#51$$$ по $$$\#55$$$). В день $$$\#56$$$ над котлованом на пятом участке появятся мостки, и Кеше не потребуется обходить этот участок. А экскаватор отправится на шестой участок, на котором он будет работать до дня $$$\#66$$$ включительно.
Однако в день $$$\#64$$$ произойдёт ещё один — десятый — прорыв. Это означает, что количество участков, которые Кеше придётся обходить, вновь станет равным $$$5$$$. На этот раз он будет обходить пять участков в течение трёх дней. В день $$$\#67$$$ над шестым участком появятся мостки, и количество участков, которые приходится обходить Кеше, опять уменьшится до $$$4$$$.
Более прорывов не происходило (или нам о них неизвестно), так что количество участков, которые Кеше придётся обходить, уже не увеличится. Как можно видеть, максимальное количество участков, которое Кеше пришлось обходить в течение одного дня, составляет $$$5$$$. А совершать обход максимального количества участков ему пришлось в течение $$$10$$$ дней $$$(2 + 5 + 3 = 10)$$$.
Осень — время, когда хочется чего-нибудь тёплого. Кеша иногда заходит в котокафе, чтобы выпить горячего кофе и, конечно, погладить котиков. Котиков в кафе достаточно много, притом разных мастей. Иногда Кеша пытается их пересчитать, но это не так-то просто.
В одно из своих посещений кафе Кеша проанализировал процесс глажения котиков.
Кеша гладил каждого котика в течение одной минуты. После этого котик мог либо уйти, либо подождать какое-то время, чтобы его погладили снова. Кеша заметил, что никакой котик не ждал более, чем $$$m$$$ минут, а также что никакого котика он не гладил более одной минуты подряд.
Известен список мастей котиков, которых гладил Кеша, в том порядке, в котором он их гладил. Ваша задача — определить минимально возможное количество котиков, которых погладил Кеша. Также, полагая, что котиков было минимальное возможное количество, нужно определить максимальное количество котиков одной масти, которых погладил Кеша.
В первой строке содержится целое число $$$n$$$ $$$(1 \le n \le 10^5)$$$ — количество записей в списке мастей.
Во второй строке содержится целое число $$$m$$$ $$$(1 \le m \le 10^5)$$$ — максимально возможное время ожидания котиком очередного поглаживания.
В каждой из следующих $$$n$$$ строк содержится по одной масти котика. Масть — непустая последовательность строчных символов латинского алфавита длиной не более $$$30$$$.
В первой строке выведите целое число — минимально возможное количество котиков, которых погладил Кеша.
Во второй строке выведите целое число — максимальное количество котиков одной масти, которых погладил Кеша.
В первых пяти подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов.
Баллы за шестую подзадачу начисляются только в случае прохождения всех тестов этой подзадачи. Участнику сообщается либо номер первого непройденного теста и результат проверки на этом тесте, либо что все тесты подзадачи пройдены
Для всех подзадач, кроме первой, требуется, чтобы программа верно решала одну или несколько из предшествующих подзадач. Более подробно разбиение на подзадачи показано в таблице ниже.
| Подзадача | Баллы за тест | Ограничения | Необходимые | Информация |
| (баллы | подзадачи | о проверке | ||
| за подзадачу) | ||||
| 1 | 1 (до 10) | $$$n \le 100$$$, $$$m = 1$$$, масть котика — | нет | полная |
| строка длиной $$$1$$$ символ | ||||
| 2 | 1 (до 10) | $$$n \le 100$$$, $$$m \le 10$$$, масть котика — | 1 | полная |
| строка длиной $$$1$$$ символ | ||||
| 3 | 2 (до 20) | $$$n \le 10^5$$$, $$$m \le 10^5$$$, масть котика — | 2 | полная |
| строка длиной $$$1$$$ символ | ||||
| 4 | 2 (до 10) | $$$n \le 10^5$$$, $$$m \le 10^5$$$, | 1 | полная |
| котики только $$$2$$$ мастей | ||||
| 5 | 2 (до 10) | $$$n \le 10^5$$$, $$$m \le 10^5$$$, | 1 | полная |
| котики только $$$3$$$ мастей | ||||
| 6 | 0 (40) | $$$n \le 10^5$$$, $$$m \le 10^5$$$ | 3, 4, 5 | первая ошибка |
14 3 gray white red gray cream white white red tabby black white black red gray
10 3
Сначала Кеша гладил серого кота, затем — белого, затем — рыжего, и после этого — снова серого кота. Это мог быть первый серый кот, поскольку в этом случае ему пришлось бы ждать $$$2$$$ минуты. Таким образом, минимальное количество различных котов, которых погладил Кеша к этому моменту, составляет $$$3$$$.
После серого кота Кеша погладит кота кремового окраса, а затем белого. Белый кот мог быть «прошлым» белым котом, поскольку он мог ждать $$$3$$$ минуты. Как можно видеть, в списке два подряд кота белой масти, и это разные коты (поскольку ни одного кота Кеша не гладил более одной минуты подряд). К этому моменту Кеша погладит ещё двух «новых» котов, итого их станет $$$5$$$. Заметим, что два белых кота — это пока максимальное количество котов одной масти.
Далее Кеша гладит рыжего кота, но это не может быть рыжий кот, которого он гладил третьим по счёту — прошло уже более $$$3$$$ минут. Это значит, что Кеша погладил уже двух рыжих котов, а минимальное количество различных котов, которых погладил Кеша, составляет теперь $$$6$$$.
После рыжего кота Кеша гладит кота расцветки табби, затем чёрного кота, и снова белого кота. Это мог быть второй белый кот, которого уже гладил Кеша, поскольку кот мог ожидать в течение $$$3$$$ минут. Следовательно, минимальное количество различных котов, которых погладил Кеша, теперь равно $$$8$$$.
Следующий кот, которого гладит Кеша, имеет чёрный окрас, и это может быть тот черный кот, которого он гладил перед белым. Минимальное количество различных котов, которых погладил Кеша, не увеличилось.
После этого Кеша гладит рыжего и серого котов, гладить которых до этого он не мог. Поэтому минимальное количество различных котов, которых погладил Кеша, составляет $$$10$$$, а максимальное количество котов одной масти будет равно $$$3$$$, поскольку Кеша погладил уже третьего рыжего кота.