Сейчас идёт праздничный сезон, и Коала декорирует свой дом разными лампами. У него есть \(n\) ламп, каждая из которых периодически моргает.
После того как Коала взглянул на лампы, он заметил, у каждой лампы есть два параметра \(a_i\) и \(b_i\). Лампа с параметрами \(a_i\) и \(b_i\) переключается (т.е. переходит из включённого состояния в выключенное или наоборот) каждую \(a_i\)-ю секунду начиная с \(b_i\)-й. Иначе говоря, она переключается (меняет своё состояние) в моменты \(b_i\), \(b_i + a_i\), \(b_i + 2 \cdot a_i\) и так далее.
Вы знаете для каждой лампы, включена она изначально или нет, а также соответствующие параметры \(a_i\) и \(b_i\). Коала интересуется, чему будет равно наибольшее число ламп, которые будут одновременно включены. Вам нужно это выяснить.
Так выглядит состояние ламп в первом примере. Выходные данные
Выведите одно число — максимальное возможное число одновременно горящих ламп.
Примечание
В первом примере состояния ламп изображены на картинке выше. Наибольшее число одновременно включённых ламп равно \(2\) (например в момент \(2\)).
Во втором примере все лампы изначально включены. Значит ответ равен \(4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
101
3 3
3 2
3 1
|
2
|
|
2
|
4
1111
3 4
5 2
3 1
3 2
|
4
|
|
3
|
6
011100
5 3
5 5
2 4
3 5
4 2
1 5
|
6
|