{"problem":{"name":"G. Гирлянда","description":{"content":"Новогодняя гирлянда после включения загорается на $A$ минут, потом гаснет на $A$ минут, потом опять загорается на $A$ минут, гаснет на $A$, и так до бесконечности. Параметр $A$ задаётся пользователем ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10218G"},"statements":[{"statement_type":"Markdown","content":"Новогодняя гирлянда после включения загорается на $A$ минут, потом гаснет на $A$ минут, потом опять загорается на $A$ минут, гаснет на $A$, и так до бесконечности. Параметр $A$ задаётся пользователем перед первым включением гирлянды и может быть любым натуральным числом.\n\nДетишки расстроятся, если во время праздников, которые начинаются в момент времени $0$ и заканчиваются в момент времени $T$, гирлянда будет гореть меньше половины времени. \n\nВ гости к детишкам на праздники приезжает дедушка, который не любит горящие гирлянды. Вам известны интервалы времени, в которые он будет присутствовать дома. Найдите такое значение параметра $A$ и время включения гирлянды, которые позволят минимизировать длительность времени нахождения дедушки дома с включенной гирляндой и при этом не приведут к расстройству детишек. Учтите, что включить гирлянду можно в любой целочисленный момент времени, в том числе до наступления праздников, но выключить её после включения уже нельзя.\n\nПервая строка содержит длительность новогодних праздников $T$ ($1 <= T <= 5000$) в минутах и количество интервалов $N$ ($0 <= N <= T \\/ 2$).\n\nВ следующих $N$ строках заданы интервалы времени, в которые дедушка будет присутствовать дома, — начало интервала $L_i$ и конец интервала $R_i$ ($0 <= L_i < R_i <= T$). Интервалы не пересекаются и упорядочены по возрастанию времени начала ($R_i < L_{i + 1}$).\n\nВсе числа во входных данных целые.\n\nВыведите три числа: минимальную длительность времени, которую дедушка вынужден будет провести дома с включённой гирляндой, искомое значение параметра $A$ и момент времени включения гирлянды.\n\nЕсли существует несколько решений, выведите решение с минимальным значением $A$. Если и таких решений существует несколько, выведите решение с самым поздним временем включения гирлянды.\n\n## Входные Данные\n\nПервая строка содержит длительность новогодних праздников $T$ ($1 <= T <= 5000$) в минутах и количество интервалов $N$ ($0 <= N <= T \\/ 2$).В следующих $N$ строках заданы интервалы времени, в которые дедушка будет присутствовать дома, — начало интервала $L_i$ и конец интервала $R_i$ ($0 <= L_i < R_i <= T$). Интервалы не пересекаются и упорядочены по возрастанию времени начала ($R_i < L_{i + 1}$).Все числа во входных данных целые.\n\n## Выходные Данные\n\nВыведите три числа: минимальную длительность времени, которую дедушка вынужден будет провести дома с включённой гирляндой, искомое значение параметра $A$ и момент времени включения гирлянды.Если существует несколько решений, выведите решение с минимальным значением $A$. Если и таких решений существует несколько, выведите решение с самым поздним временем включения гирлянды.\n\n## Примеры\n\nВходные данные10 2\n1 4\n7 10\nВыходные данные2 1 0\nВходные данные8 2\n1 3\n5 7\nВыходные данные0 2 -1\nВходные данные6 1\n0 4\nВыходные данные1 3 3\nВходные данные5 1\n0 5\nВыходные данные3 1 0\nВходные данные4 0\nВыходные данные0 1 1\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z}^+ $ be the duration of the holiday period $[0, T]$.  \nLet $ N \\in \\mathbb{Z}_{\\geq 0} $ be the number of intervals during which the grandfather is home.  \nLet $ \\mathcal{I} = \\{ (L_i, R_i) \\mid i \\in \\{1, \\dots, N\\} \\} $ be a set of non-overlapping, sorted intervals with $ 0 \\leq L_i < R_i < T $ and $ R_i < L_{i+1} $.  \n\nLet $ A \\in \\mathbb{Z}^+ $ be the period parameter: the garland alternates between ON for $ A $ minutes and OFF for $ A $ minutes, starting at some integer activation time $ t_0 \\in \\mathbb{Z} $ (possibly $ t_0 < 0 $).  \nThe garland is ON during intervals $ [t_0 + 2kA, t_0 + (2k+1)A) $, $ k \\in \\mathbb{Z} $.  \n\n**Constraints**  \n1. The garland must illuminate at least half the holiday time:  \n   $$\n   \\mu\\left( [0, T] \\cap \\bigcup_{k \\in \\mathbb{Z}} [t_0 + 2kA, t_0 + (2k+1)A) \\right) \\geq \\frac{T}{2}\n   $$  \n2. $ t_0 \\in \\mathbb{Z} $, $ A \\in \\mathbb{Z}^+ $.  \n\n**Objective**  \nMinimize the total time the grandfather spends home with the garland ON:  \n$$\n\\sum_{i=1}^{N} \\mu\\left( [L_i, R_i] \\cap \\bigcup_{k \\in \\mathbb{Z}} [t_0 + 2kA, t_0 + (2k+1)A) \\right)\n$$  \nsubject to the above constraint.  \n\nAmong all minimizing triples $ (A, t_0, \\text{min\\_time}) $, choose the one with:  \n- Minimal $ A $,  \n- Then maximal $ t_0 $.  \n\nOutput: $ (\\text{min\\_time}, A, t_0) $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10218G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}