Новогодняя гирлянда после включения загорается на $$$A$$$ минут, потом гаснет на $$$A$$$ минут, потом опять загорается на $$$A$$$ минут, гаснет на $$$A$$$, и так до бесконечности. Параметр $$$A$$$ задаётся пользователем перед первым включением гирлянды и может быть любым натуральным числом.
Детишки расстроятся, если во время праздников, которые начинаются в момент времени $$$0$$$ и заканчиваются в момент времени $$$T$$$, гирлянда будет гореть меньше половины времени.
В гости к детишкам на праздники приезжает дедушка, который не любит горящие гирлянды. Вам известны интервалы времени, в которые он будет присутствовать дома. Найдите такое значение параметра $$$A$$$ и время включения гирлянды, которые позволят минимизировать длительность времени нахождения дедушки дома с включенной гирляндой и при этом не приведут к расстройству детишек. Учтите, что включить гирлянду можно в любой целочисленный момент времени, в том числе до наступления праздников, но выключить её после включения уже нельзя.
Первая строка содержит длительность новогодних праздников $$$T$$$ ($$$1 \le T \le 5000$$$) в минутах и количество интервалов $$$N$$$ ($$$0 \le N \le T/2$$$).
В следующих $$$N$$$ строках заданы интервалы времени, в которые дедушка будет присутствовать дома, — начало интервала $$$L_i$$$ и конец интервала $$$R_i$$$ ($$$0 \le L_i \lt R_i \le T$$$). Интервалы не пересекаются и упорядочены по возрастанию времени начала ($$$R_i \lt L_{i+1}$$$).
Все числа во входных данных целые.
Выведите три числа: минимальную длительность времени, которую дедушка вынужден будет провести дома с включённой гирляндой, искомое значение параметра $$$A$$$ и момент времени включения гирлянды.
Если существует несколько решений, выведите решение с минимальным значением $$$A$$$. Если и таких решений существует несколько, выведите решение с самым поздним временем включения гирлянды.
10 2 1 4 7 10
2 1 0
8 2 1 3 5 7
0 2 -1
6 1 0 4
1 3 3
5 1 0 5
3 1 0
4 0
0 1 1
