#include <bits/stdc++.h>
using namespace std;
const int md = 1e9 + 7;
const long long inf64 = 1e18;
int sz = 1;
vector<pair<int, int>> tr;
vector<int> ps;
pair<int, int> merge(pair<int, int> &a, pair<int, int> &b) {
  if (a.first < b.first) return a;
  if (a.first > b.first) return b;
  return {a.first, a.second + b.second};
}
void build(int v, int l, int r, int bg, int en) {
  if (bg >= r || l >= en) return;
  if (r - l == 1) {
    tr[v] = {0, r - l};
    return;
  }
  int m = (l + r) >> 1;
  build(v << 1, l, m, bg, en);
  build(v << 1 | 1, m, r, bg, en);
  tr[v] = merge(tr[v << 1], tr[v << 1 | 1]);
}
void push(int v, int l, int r) {
  ps[v << 1] += ps[v];
  ps[v << 1 | 1] += ps[v];
  tr[v << 1].first += ps[v];
  tr[v << 1 | 1].first += ps[v];
  ps[v] = 0;
}
void add(int v, int l, int r, int bg, int en, int val) {
  if (bg >= r || l >= en) return;
  if (l >= bg && r <= en) {
    ps[v] += val;
    tr[v].first += val;
    return;
  }
  push(v, l, r);
  int m = (l + r) >> 1;
  add(v << 1, l, m, bg, en, val), add(v << 1 | 1, m, r, bg, en, val);
  tr[v] = merge(tr[v << 1], tr[v << 1 | 1]);
}
vector<int> v;
unordered_map<int, int> cn, l, r;
unordered_map<int, set<int>> whr;
void modify(int i, int old, int nw) {
  if (old != -1) {
    whr[old].erase(i);
    cn[old]--;
    if (cn[old] == 0)
      cn.erase(old);
    else {
      l[old] = *whr[old].begin();
      r[old] = *whr[old].rbegin();
    }
  }
  whr[nw].insert(i);
  cn[nw]++;
  l[nw] = *whr[nw].begin();
  r[nw] = *whr[nw].rbegin();
  v[i] = nw;
}
void change(int i, int x) {
  int old = v[i];
  if (old != -1) add(1, 0, sz, l[old], r[old], -1);
  if (cn.count(x)) add(1, 0, sz, l[x], r[x], -1);
  modify(i, old, x);
  if (old != -1) add(1, 0, sz, l[old], r[old], 1);
  if (cn.count(x)) add(1, 0, sz, l[x], r[x], 1);
}
int main() {
  iostream::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  vector<int> on(n);
  for (int i = 0; i < n; i++) {
    char c;
    cin >> c;
    on[i] = c - '0';
  }
  for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
  int mx = 0;
  for (int i = 0; i < 1e6; i++) {
    int cur = 0;
    for (int j = 0; j < n; j++) {
      if (on[j]) cur++;
      if (i + 1 >= b[j] && (i + 1 - b[j]) % a[j] == 0) on[j] ^= true;
    }
    mx = max(mx, cur);
  }
  cout << mx << '\n';
  return 0;
}

### Prompt

Generate a cpp solution to the following problem:

It is a holiday season, and Koala is decorating his house with cool lights! He owns n lights, all of which flash periodically.

After taking a quick glance at them, Koala realizes that each of his lights can be described with two parameters a_i and b_i. Light with parameters a_i and b_i will toggle (on to off, or off to on) every a_i seconds starting from the b_i-th second. In other words, it will toggle at the moments b_i, b_i + a_i, b_i + 2 ⋅ a_i and so on.

You know for each light whether it's initially on or off and its corresponding parameters a_i and b_i. Koala is wondering what is the maximum number of lights that will ever be on at the same time. So you need to find that out.

<image> Here is a graphic for the first example.

Input

The first line contains a single integer n (1 ≤ n ≤ 100), the number of lights.

The next line contains a string s of n characters. The i-th character is "1", if the i-th lamp is initially on. Otherwise, i-th character is "0".

The i-th of the following n lines contains two integers a_i and b_i (1 ≤ a_i, b_i ≤ 5) — the parameters of the i-th light.

Output

Print a single integer — the maximum number of lights that will ever be on at the same time.

Examples

Input


3
101
3 3
3 2
3 1


Output


2


Input


4
1111
3 4
5 2
3 1
3 2


Output


4


Input


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


Output


6

Note

For first example, the lamps' states are shown in the picture above. The largest number of simultaneously on lamps is 2 (e.g. at the moment 2).

In the second example, all lights are initially on. So the answer is 4.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int md = 1e9 + 7;
const long long inf64 = 1e18;
int sz = 1;
vector<pair<int, int>> tr;
vector<int> ps;
pair<int, int> merge(pair<int, int> &a, pair<int, int> &b) {
  if (a.first < b.first) return a;
  if (a.first > b.first) return b;
  return {a.first, a.second + b.second};
}
void build(int v, int l, int r, int bg, int en) {
  if (bg >= r || l >= en) return;
  if (r - l == 1) {
    tr[v] = {0, r - l};
    return;
  }
  int m = (l + r) >> 1;
  build(v << 1, l, m, bg, en);
  build(v << 1 | 1, m, r, bg, en);
  tr[v] = merge(tr[v << 1], tr[v << 1 | 1]);
}
void push(int v, int l, int r) {
  ps[v << 1] += ps[v];
  ps[v << 1 | 1] += ps[v];
  tr[v << 1].first += ps[v];
  tr[v << 1 | 1].first += ps[v];
  ps[v] = 0;
}
void add(int v, int l, int r, int bg, int en, int val) {
  if (bg >= r || l >= en) return;
  if (l >= bg && r <= en) {
    ps[v] += val;
    tr[v].first += val;
    return;
  }
  push(v, l, r);
  int m = (l + r) >> 1;
  add(v << 1, l, m, bg, en, val), add(v << 1 | 1, m, r, bg, en, val);
  tr[v] = merge(tr[v << 1], tr[v << 1 | 1]);
}
vector<int> v;
unordered_map<int, int> cn, l, r;
unordered_map<int, set<int>> whr;
void modify(int i, int old, int nw) {
  if (old != -1) {
    whr[old].erase(i);
    cn[old]--;
    if (cn[old] == 0)
      cn.erase(old);
    else {
      l[old] = *whr[old].begin();
      r[old] = *whr[old].rbegin();
    }
  }
  whr[nw].insert(i);
  cn[nw]++;
  l[nw] = *whr[nw].begin();
  r[nw] = *whr[nw].rbegin();
  v[i] = nw;
}
void change(int i, int x) {
  int old = v[i];
  if (old != -1) add(1, 0, sz, l[old], r[old], -1);
  if (cn.count(x)) add(1, 0, sz, l[x], r[x], -1);
  modify(i, old, x);
  if (old != -1) add(1, 0, sz, l[old], r[old], 1);
  if (cn.count(x)) add(1, 0, sz, l[x], r[x], 1);
}
int main() {
  iostream::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  vector<int> on(n);
  for (int i = 0; i < n; i++) {
    char c;
    cin >> c;
    on[i] = c - '0';
  }
  for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
  int mx = 0;
  for (int i = 0; i < 1e6; i++) {
    int cur = 0;
    for (int j = 0; j < n; j++) {
      if (on[j]) cur++;
      if (i + 1 >= b[j] && (i + 1 - b[j]) % a[j] == 0) on[j] ^= true;
    }
    mx = max(mx, cur);
  }
  cout << mx << '\n';
  return 0;
}

```