У Вовы довольно странный режим сна. В сутках \(h\) часов. Вова будет спать ровно \(n\) раз. В \(i\)-й раз он будет спать ровно после \(a_i\) часов после пробуждения. Предположим, что Вова просыпается ровно в начале этой истории (изначальное время равно \(0\)). Каждый раз Вова спит ровно сутки (другими словами, \(h\) часов).
Вова думает, что \(i\)-й раз, когда он спит, — хороший, если он идет спать между \(l\) и \(r\) часами включительно.
Вова может контролировать себя и перед \(i\)-м разом он может выбрать одно из двух: пойти спать после \(a_i\) часов или после \(a_i - 1\) часов.
Ваша задача — назвать максимальное число хороших раз, которые Вова может получить, если будет действовать оптимально.
Выходные данные
Выведите одно целое число — максимальное количество хороших раз, которое Вова может получить, если будет действовать оптимально.
Примечание
Максимальное количество хороших раз в тестовом примере равно \(3\).
История начинается с \(t=0\). Затем Вова идет спать после \(a_1 - 1\) часов, теперь время равно \(15\). Это время не является хорошим. Затем Вова идет спать после \(a_2 - 1\) часов, теперь время равно \(15 + 16 = 7\). Это время также не является хорошим. Затем Вова идет спать после \(a_3\) часов, теперь время равно \(7 + 14 = 21\). Это время является хорошим. Затем Вова идет спать после \(a_4 - 1\) часов, теперь время равно \(21 + 19 = 16\). Это время не является хорошим. Затем Вова идет спать после \(a_5\) часов, теперь время равно \(16 + 20 = 12\). Это время не является хорошим. Затем Вова идет спать после \(a_6\) часов, Теперь время равно \(12 + 11 = 23\). Это время является хорошим. Затем Вова идет спать после \(a_7\) часов, теперь время равно \(23 + 22 = 21\). Это время также является хорошим.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 24 21 23
16 17 14 20 20 11 22
|
3
|