시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 66 29 16 53.333%

문제

제국과 왕국은 오래 전부터 사이가 좋지 않았다. 결국 1주일 전 제국은 왕국에 전쟁을 선포했고, 전투마다 승승장구하며 왕국의 성 앞까지 진격해왔다.

왕국의 성은 마법 장벽으로 보호되고 있어, 성을 공격하기 위해서는 이 장벽을 뚫을 수 있는 마법 대포를 사용해야 한다. 장벽은 N겹의 막이 서로 붙어있는 형태이고, 성의 바깥쪽부터 안쪽으로 1부터 N까지의 자연수 번호가 차례대로 붙어있다. 또한 각 막의 두께는 1이며 좌우로 무한히 멀리 뻗어있다. i (1 ≤ i  ≤ N)번째 막에는 좌우 길이 Li의 패턴이 있는데, 패턴은 길이 1의 칸으로 이루어져 있으며 각 칸은 1 또는 0으로 표현된다. 1은 마법 포탄이 지나갈 수 있는 칸이고, 0은 마법 포탄이 지나갈 수 없는 칸이다. i번째 막에는 이러한 패턴이 Li 칸마다 주기적으로 무한히 이어지게 된다.

예를 들어 패턴이 01101인 막을 그림으로 표현하면 아래와 같다. 0, 3번째 칸은 마법 포탄이 지나갈 수 없고, 1, 2, 4번째 칸은 마법 포탄이 지나갈 수 있다. 이 패턴이 무한히 반복되어 5, 8번째 칸과 -5, -2번째 칸 등도 마법 포탄이 지나갈 수 없고, 6, 7, 9번째 칸과 -4, -3, -1번째 칸 등은 마법 포탄이 지나갈 수 있다. 포탄이 지나갈 수 없는 칸에 포탄이 도달하면 그 포탄은 그 자리에서 소멸된다.

제국은 1번째 막에서 1만큼 떨어진 곳에 마법 대포들을 설치하고 총 M발의 마법 포탄을 쏘았다. i번째 마법 포탄은 Pi의 위치에서 Di 방향으로 쏘아지는데, 1초마다 막을 1개씩 순서대로 통과하며, 막을 하나 통과할 때마다 Di만큼씩 옆으로 이동하게 된다. 예를 들어 어떤 마법 대포를 3의 위치에서 -2 방향으로 쏘았다면 첫 번째 막에 도달할 때는 1, 두 번째 막에 도달할 때는 -1의 위치에 가게 된다. 포탄은 매 초마다 순간이동하기 때문에, 이동하는 도중 다른 칸의 영향은 받지 않는다. 마법 포탄이 모든 막을 통과하게 되면 왕국의 성에 피해를 입히게 된다.

왕국의 성의 패턴과 제국이 쏜 마법 포탄들의 위치와 방향이 주어질 때, 이 중 성에 피해를 준 마법 포탄은 총 몇 개일까?

입력

첫째 줄에 마법 장벽의 막의 수 N(1 ≤ N ≤ 10,000) 과 제국이 쏜 마법 포탄의 수 M(1 ≤ M ≤ 200,000) 이 공백을 사이에 두고 주어진다.

둘째 줄부터 N개의 줄에는 마법 장벽에 대한 정보가 주어진다. i+1번째 줄에는 i번째 막의 패턴의 길이 L(1 ≤ Li ≤ 6) 와 길이 Li의 패턴이 공백을 사이에 두고 주어진다.

그 다음 줄부터 M개의 줄에는 제국이 쏜 마법 포탄에 대한 정보가 주어진다. N+i+1번째 줄에는 i번째 포탄의 발사 위치 Pi와 발사 방향 Di (-100,000 ≤ Pi, Di ≤ 100,000)가 공백을 사이에 두고 주어진다.

입력으로 주어지는 수는 모두 정수이다.

출력

첫째 줄에 왕국의 성에 피해를 입힌 마법 포탄의 수를 출력한다.

예제 입력 1

3 7
4 0111
3 101
5 11101
2 0
2 -1
-2 1
-10 5
0 0
0 1
9 -4

예제 출력 1

4

예제를 그림으로 표현하면 다음과 같다. 회색 칸들 중 수가 쓰인 곳들에 마법 대포가 있고, 그 수의 방향으로 포탄을 쏜다. 아래의 세 줄은 위에서부터 각각 1, 2, 3번째 막을 나타낸다. 1~4번째 포탄이 성에 피해를 입히게 된다.


 

출처