← 返回题目列表

Codeforces · 1209/B

B. 考拉和灯

中文机器翻译题面 查看原题

放假了,考拉正在用炫酷的灯光装饰他的房子!他拥有 $$$n$$$ 灯,所有这些灯都会定期闪烁。

快速浏览了它们之后,Koala 意识到他的每个灯都可以用两个参数 $$$a_i$$$ 和 $$$b_i$$$ 来描述。具有参数 $$$a_i$$$ 和 $$$b_i$$$ 的灯光将从第 $$$b_i$$$ 秒开始每 $$$a_i$$$ 秒切换一次(打开到关闭,或关闭到打开)。换句话说,它将在 $$$b_i$$$、$$$b_i + a_i$$$、$$$b_i + 2 \cdot a_i$$$ 等时刻切换。

您知道每个灯最初是打开还是关闭以及其相应的参数 $$$a_i$$$ 和 $$$b_i$$$。考拉想知道同时亮起的灯的最大数量是多少。所以你需要找出答案。

这是第一个示例的图形。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$),即灯光数量。

下一行包含 $$$s$$$ 个字符的字符串 $$$n$$$。如果第 $$$i$$$ 个灯最初亮起,则第 $$$i$$$ 个字符为“1”。否则,第 $$$i$$$ 个字符为“0”。

以下 $$$n$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i, b_i \le 5$$$) — 第 $$$i$$$ 灯的参数。

输出

打印一个整数——同时打开的最大灯数。

示例

输入 #1

3
101
3 3
3 2
3 1

输出 #1

2

输入 #2

4
1111
3 4
5 2
3 1
3 2

输出 #2

4

输入 #3

6
011100
5 3
5 5
2 4
3 5
4 2
1 5

输出 #3

6

注意

第一个例子,灯的状态如上图所示。同时亮灯的最大数量为 $$$2$$$(例如目前 $$$2$$$)。

在第二个示例中,所有灯最初都是打开的。所以答案是$$$4$$$。