Новогодняя гирлянда после включения загорается на $A$ минут, потом гаснет на $A$ минут, потом опять загорается на $A$ минут, гаснет на $A$, и так до бесконечности. Параметр $A$ задаётся пользователем перед первым включением гирлянды и может быть любым натуральным числом.
Детишки расстроятся, если во время праздников, которые начинаются в момент времени $0$ и заканчиваются в момент времени $T$, гирлянда будет гореть меньше половины времени.
В гости к детишкам на праздники приезжает дедушка, который не любит горящие гирлянды. Вам известны интервалы времени, в которые он будет присутствовать дома. Найдите такое значение параметра $A$ и время включения гирлянды, которые позволят минимизировать длительность времени нахождения дедушки дома с включенной гирляндой и при этом не приведут к расстройству детишек. Учтите, что включить гирлянду можно в любой целочисленный момент времени, в том числе до наступления праздников, но выключить её после включения уже нельзя.
Первая строка содержит длительность новогодних праздников $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}$).
Все числа во входных данных целые.
Выведите три числа: минимальную длительность времени, которую дедушка вынужден будет провести дома с включённой гирляндой, искомое значение параметра $A$ и момент времени включения гирлянды.
Если существует несколько решений, выведите решение с минимальным значением $A$. Если и таких решений существует несколько, выведите решение с самым поздним временем включения гирлянды.
## Входные Данные
Первая строка содержит длительность новогодних праздников $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}$).Все числа во входных данных целые.
## Выходные Данные
Выведите три числа: минимальную длительность времени, которую дедушка вынужден будет провести дома с включённой гирляндой, искомое значение параметра $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
[samples]
**Definitions**
Let $ T \in \mathbb{Z}^+ $ be the duration of the holiday period $[0, T]$.
Let $ N \in \mathbb{Z}_{\geq 0} $ be the number of intervals during which the grandfather is home.
Let $ \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} $.
Let $ 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 $).
The garland is ON during intervals $ [t_0 + 2kA, t_0 + (2k+1)A) $, $ k \in \mathbb{Z} $.
**Constraints**
1. The garland must illuminate at least half the holiday time:
$$
\mu\left( [0, T] \cap \bigcup_{k \in \mathbb{Z}} [t_0 + 2kA, t_0 + (2k+1)A) \right) \geq \frac{T}{2}
$$
2. $ t_0 \in \mathbb{Z} $, $ A \in \mathbb{Z}^+ $.
**Objective**
Minimize the total time the grandfather spends home with the garland ON:
$$
\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)
$$
subject to the above constraint.
Among all minimizing triples $ (A, t_0, \text{min\_time}) $, choose the one with:
- Minimal $ A $,
- Then maximal $ t_0 $.
Output: $ (\text{min\_time}, A, t_0) $.