27090번 - 지뢰 피하기

문제

마인크래프트를 좋아하는 수학토끼는 마인크래프트와 지뢰찾기를 섞어 $N$행 $M$열 직사각형 격자에서 할 수 있는 재미있는 게임을 만들었다. 게임의 규칙은 다음과 같다:

• 격자에 $K$개의 아이템이 배치되어 있다. 한 칸에 아이템은 최대 하나 있을 수 있다.
• 아이템이 없는 칸에 $T$개의 지뢰가 배치되어 있다. 한 칸에 지뢰는 최대 하나 존재한다. 또한 각 지뢰는 고유한 숫자 $W_i$를 가지며, $W_i$개 이상의 아이템을 가진 상태로 그 지뢰를 밟으면 지뢰가 터진다.
• 플레이어는 상하좌우 칸 중 하나로 이동할 수 있다. 단, 격자 밖으로 나갈 수 없다.
• 이 격자와 외부를 연결하는 통로는 하나이다. 즉, 출입구 칸에서부터 시작하여 다시 출입구 칸으로 돌아와야 한다.
• 아이템이 있는 칸에 가면 아이템을 얻을 수 있으며, 이 때 아이템을 얻을지 여부는 선택할 수 있다. 단, 한 번 얻은 아이템은 다시 버릴 수 없다.

예를 들어 아래 예제 1과 같은 상황을 보자. 이 경우 2개 이상의 아이템을 얻을 수 없다. 1번 아이템을 얻으면 2번 아이템도 얻고 돌아올 수 없고, 2번 아이템을 얻으면 1번 아이템도 얻고 돌아올 수 없기 때문이다.

수학토끼는 직사각형 격자에 대한 조사를 미리 다 했기 때문에 출입구 칸과 아이템의 위치, 지뢰의 위치 및 고유 숫자를 모두 알고 있다. 지뢰가 터지지 않도록 하면서 얻을 수 있는 아이템의 최대 개수를 출력하는 프로그램을 작성하라.

입력

첫 줄에 두 정수 $N$과 $M$이 주어진다.

둘째 줄에 출입구 칸의 좌표 $X_d$와 $Y_d$가 주어진다.

셋째 줄에 아이템의 개수 $K$가 주어진다.

넷째 줄부터 $K+3$번째 줄까지 $K$개의 아이템의 위치 정보가 주어진다. 구체적으로 $i+2$번째 줄에는 $i$번째 아이템의 좌표 $X_i$와 $Y_i$가 주어진다.

$K+4$째 줄에 지뢰의 개수 $T$가 주어진다.

$K+5$째 줄부터 $K+T+4$째 줄까지 $T$개의 지뢰의 정보가 주어진다. 구체적으로 $i+K+4$번째 줄에는 $i$번째 지뢰의 좌표 $P_i$와 $Q_i,ドル 그리고 고유 숫자 $W_i$가 주어진다.

출력

지뢰가 터지지 않도록 하면서 얻을 수 있는 아이템의 최대 개수를 출력한다.

제한

• 1ドル \le N \le 10^3$
• 1ドル \le M \le 10^3$
• 0ドル \le K+T < NM$
• 1ドル \le X_d \le N$
• 1ドル \le Y_d \le M$
• 1ドル \le X_i \le N~(1 \le i \le K)$
• 1ドル \le Y_i \le M~(1 \le i \le K)$
• 1ドル \le P_i \le N~(1 \le i \le T)$
• 1ドル \le Q_i \le M~(1 \le i \le T)$
• 0ドル \le W_i \le NM~(1 \le i \le T)$
• $(X_d, Y_d),ドル $(X_i, Y_i)$ (1ドル \le i \le K),ドル $(P_i, Q_i)$ (1ドル \le i \le T$)는 모두 서로 다르다.

힌트