#include <bits/stdc++.h>
long long MAX = -100000000000;
long long MIN = -100000000000;
long long MOD = 1000000007;
long long longlongmax = 9223372036854775807LL;
long long maxormin(long long a, long long b, long long flag) {
  return flag == 1 ? (a > b ? a : b) : (a < b ? a : b);
}
long long overflowcheck(long long a) {
  if (a == 1) {
    return 0;
  } else {
    long long temp = a;
    long long power = 1;
    while (longlongmax / temp > a) {
      temp *= a;
      power++;
    }
    return power + 1;
  }
}
long long merge(long long A[], long long B[], long long left, long long mid,
                long long right) {
  long long count = 0;
  long long n1 = mid - left + 1;
  long long n2 = right - mid;
  long long LA[n1], LB[n1], RA[n1], RB[n2];
  for (long long n = 0; n < n1; n++) {
    LA[n] = A[n + left];
    LB[n] = B[n + left];
  }
  for (long long n = 0; n < n2; n++) {
    RA[n] = A[n + mid + 1];
    RB[n] = B[n + mid + 1];
  }
  long long i = 0, j = 0, k = left;
  while (i < n1 && j < n2) {
    if (LA[i] < RA[j]) {
      A[k] = LA[i];
      B[k] = LB[i];
      i++;
    } else {
      A[k] = RA[j];
      B[k] = RB[j];
      count += n1 - i;
      j++;
    }
    k++;
  }
  while (i < n1) {
    A[k] = LA[i];
    B[k] = LB[i];
    i++;
    k++;
  }
  while (j < n2) {
    A[k] = RA[j];
    B[k] = RB[j];
    j++;
    k++;
  }
  return count;
}
long long mergesort(long long A[], long long B[], long long left,
                    long long right) {
  long long total = 0;
  if (left < right) {
    long long mid = (right - left) / 2 + left;
    total += mergesort(A, B, left, mid);
    total += mergesort(A, B, mid + 1, right);
    total += merge(A, B, left, mid, right);
  }
  return total;
}
long long on[300000];
long long status[1000][1000];
int main(int argc, char const *argv[]) {
  long long T = 1;
  for (long long t = 0; t < T; t++) {
    long long N;
    scanf("%lld", &N);
    char E[30000];
    scanf("%s", E);
    for (long long i = 0; i < N; i++) {
      if (E[i] - '0') {
        on[i] = 1;
        status[i][0] = on[i];
      }
    }
    long long A[N], B[N];
    for (long long n = 0; n < N; n++) {
      scanf("%lld %lld", &A[n], &B[n]);
    }
    for (long long n = 0; n < N; n++) {
      long long tim = B[n];
      long long prev = status[n][0];
      long long prevind = 0;
      while (tim < 1000) {
        for (long long i = prevind; i < tim; i++) {
          status[n][i] = status[n][prevind];
        }
        status[n][tim] = prev ^ 1;
        prev = status[n][tim];
        prevind = tim;
        tim += A[n];
      }
    }
    for (long long i = 0; i < 1000; i++) {
      long long cnt = 0;
      for (long long n = 0; n < N; n++) {
        cnt += status[n][i];
      }
      if (MAX < cnt) {
        MAX = cnt;
      }
    }
    printf("%lld\n", MAX);
  }
  return 0;
}

### Prompt

Your challenge is to write 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>
long long MAX = -100000000000;
long long MIN = -100000000000;
long long MOD = 1000000007;
long long longlongmax = 9223372036854775807LL;
long long maxormin(long long a, long long b, long long flag) {
  return flag == 1 ? (a > b ? a : b) : (a < b ? a : b);
}
long long overflowcheck(long long a) {
  if (a == 1) {
    return 0;
  } else {
    long long temp = a;
    long long power = 1;
    while (longlongmax / temp > a) {
      temp *= a;
      power++;
    }
    return power + 1;
  }
}
long long merge(long long A[], long long B[], long long left, long long mid,
                long long right) {
  long long count = 0;
  long long n1 = mid - left + 1;
  long long n2 = right - mid;
  long long LA[n1], LB[n1], RA[n1], RB[n2];
  for (long long n = 0; n < n1; n++) {
    LA[n] = A[n + left];
    LB[n] = B[n + left];
  }
  for (long long n = 0; n < n2; n++) {
    RA[n] = A[n + mid + 1];
    RB[n] = B[n + mid + 1];
  }
  long long i = 0, j = 0, k = left;
  while (i < n1 && j < n2) {
    if (LA[i] < RA[j]) {
      A[k] = LA[i];
      B[k] = LB[i];
      i++;
    } else {
      A[k] = RA[j];
      B[k] = RB[j];
      count += n1 - i;
      j++;
    }
    k++;
  }
  while (i < n1) {
    A[k] = LA[i];
    B[k] = LB[i];
    i++;
    k++;
  }
  while (j < n2) {
    A[k] = RA[j];
    B[k] = RB[j];
    j++;
    k++;
  }
  return count;
}
long long mergesort(long long A[], long long B[], long long left,
                    long long right) {
  long long total = 0;
  if (left < right) {
    long long mid = (right - left) / 2 + left;
    total += mergesort(A, B, left, mid);
    total += mergesort(A, B, mid + 1, right);
    total += merge(A, B, left, mid, right);
  }
  return total;
}
long long on[300000];
long long status[1000][1000];
int main(int argc, char const *argv[]) {
  long long T = 1;
  for (long long t = 0; t < T; t++) {
    long long N;
    scanf("%lld", &N);
    char E[30000];
    scanf("%s", E);
    for (long long i = 0; i < N; i++) {
      if (E[i] - '0') {
        on[i] = 1;
        status[i][0] = on[i];
      }
    }
    long long A[N], B[N];
    for (long long n = 0; n < N; n++) {
      scanf("%lld %lld", &A[n], &B[n]);
    }
    for (long long n = 0; n < N; n++) {
      long long tim = B[n];
      long long prev = status[n][0];
      long long prevind = 0;
      while (tim < 1000) {
        for (long long i = prevind; i < tim; i++) {
          status[n][i] = status[n][prevind];
        }
        status[n][tim] = prev ^ 1;
        prev = status[n][tim];
        prevind = tim;
        tim += A[n];
      }
    }
    for (long long i = 0; i < 1000; i++) {
      long long cnt = 0;
      for (long long n = 0; n < N; n++) {
        cnt += status[n][i];
      }
      if (MAX < cnt) {
        MAX = cnt;
      }
    }
    printf("%lld\n", MAX);
  }
  return 0;
}

```