연습문제

나무 공격

난이도
Lv. 2
제출
727 명
참가자
568 명
정답률
80.47 %
지원 언어
C
C++
Java
Python
JavaScript
언어별 시간/메모리
언어별 시간/메모리 표
언어 시간 메모리
C 1초 1024MB
JavaScript 1초 1024MB
Python 1초 1024MB
Java 1초 1024MB
C++ 1초 1024MB

환경 파괴범 때문에 화가 난 숲의 요정은 나무 공격을 진행하려 합니다. 나무 공격 진행시 투사체 5개가 생성되어 지정된 방향으로 전진합니다. 각 투사체와 최초로 접촉한 환경 파괴범은 사라지게 되며 이때 투사체 역시 동시에 사라지게 됩니다. 만약 투사체가 환경 파괴범과 마주치지 않는다면 조용히 사라지게 됩니다.


이는 크기의 격자에서 진행됩니다. 초기에 격자의 각 칸에는 숫자 0 또는 1이 적혀있으며 0은 비어있음을, 1은 환경 파괴범이 해당 위치에 서있음을 뜻합니다.



숲의 요정은 항상 격자의 왼쪽 방향에서 나무 공격을 진행하며, 총 2회 진행합니다. 공격은 특정 행 부터 행 까지의 구간에 한하여 투사체를 만들어 진행하게 되며, 모든 투사체는 행 변화 없이 정확히 오른쪽 방향으로만 진행하게 됩니다. 투사체는 처음으로 만나는 환경 파괴범과 함께 사라지게 되며, 끝까지 만나지 않는 투사체는 조용히 사라지게 됩니다. 의 차이는 항상 4이기 때문에 투사체는 항상 5개가 만들어짐에 유의합니다. 다음은 1~5 행에 걸쳐 공격을 진행한 경우입니다.


그 다음 두 번째 공격이 2~6 행에 걸쳐 진행되면, 다음과 같은 결과를 얻게 됩니다.



따라서 위의 예시에서는 2번의 공격 이후 남아있는 서로 다른 환경 파괴범의 수가 2명이 됩니다.


초기 격자의 정보와 2번의 공격에 대한 정보가 주어졌을 때, 공격을 순서대로 진행한 이후 격자에 남아있는 서로 다른 환경 파괴범의 수를 구하는 프로그램을 작성해보세요.


본 문제의 저작권은 (주)브랜치앤바운드에 있으며, 저작자의 동의 없이 무단 전재/복제/배포를 금지합니다.

제약조건

[조건 1] 5 ≤ n, m ≤ 100

[조건 2] 1 ≤ L1, L2, R1, R2 ≤ n

입력형식

첫 번째 줄에는 격자의 크기를 나타내는 이 공백을 사이에 두고 주어집니다.


두 번째 줄부터는 개의 줄에 걸쳐 각 행에 해당하는 개의 격자 정보가 공백을 사이에 두고 주어집니다. 격자 내 숫자는 0, 1로만 주어지며 0은 비어있는 칸을, 1은 환경 파괴범이 있는 칸임을 뜻합니다.

번째 줄에는 첫 번째 공격 정보에 해당하는 값이 공백을 사이에 두고 주어집니다. 이는 번째 행부터 번째 행까지 공격이 이루어짐을 뜻하며, 은 항상 4임을 가정해도 좋습니다.

번째 줄에는 두 번째 공격 정보에 해당하는 값이 공백을 사이에 두고 주어집니다. 이는 번째 행부터 번째 행까지 공격이 이루어짐을 뜻하며, 는 항상 4임을 가정해도 좋습니다.

출력형식

첫 번째 줄에 두 번의 공격 이후 격자에 남아있는 서로 다른 환경 파괴범의 수를 출력합니다.

입력예제1

6 8 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 5 2 6

출력예제1

2

입력예제2

8 8 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 4 8

출력예제2

54