Plants vs. Zombies

Plants vs. Zombies (PvZ)는 매우 인기 있는 비디오 게임이다. 식물과 좀비가 게임의 주역이다. 게임에서 식물은 방어하고 좀비는 공격한다. 이 게임에는 "Protect Your Brains", "Bowling" 등 여러 가지 도전 모드가 있다. 그중 가장 고전적인 것은 플레이어가 식물을 조종해 좀비의 공격을 막거나, 반대로 좀비를 조종해 식물을 공격하는 것이다.

이 문제는 좀비가 식물을 공격하는 상황을 다룬다. 이 문제에서 사용하는 규칙은 실제 게임과 같지 않다. 식물과 좀비, 두 가지 역할이 있다. 각 식물은 공격 가능한 위치 집합을 가지며 그 위치들을 방어한다. 좀비의 공격 방식은 식물이 있는 위치로 걸어가 식물을 먹어버리는 것이다.

게임 맵은 N행 M열 격자로 나타낼 수 있다. 행은 위에서 아래로 0부터 N−1까지 번호가 매겨진다. 열은 왼쪽에서 오른쪽으로 0부터 M−1까지 번호가 매겨진다. 단순화를 위해 격자의 모든 칸에 식물이 하나씩 있다고 하자. r행 c열의 식물을 Pr, c라고 부른다.

식물에는 공격형, 방어형, 돈 생산형 등 여러 종류가 있다. 각 식물의 설명을 단순화하기 위해 Score와 Attack을 다음과 같이 정의한다.

좀비는 반드시 맵의 오른쪽에서 들어와야 하며, 가로로만 이동할 수 있다. 좀비가 공격하는 유일한 방법은 식물이 있는 위치로 걸어가 식물을 먹는 것이다. 따라서 좀비는 항상 오른쪽에서 공격을 시작한다. 다시 말해 r행에서 공격하려면 좀비는 먼저 Pr, M−1을 공격해야 한다. 식물 Pr, c를 공격하려면 먼저 식물 Pr, M−1, Pr, M−2, …, Pr, c를 차례로 공격해 파괴해야 한다. (r, c) 위치까지 이동해야 그곳의 식물을 공격할 수 있다.

이 문제에서 식물의 공격력은 무한하다. 좀비가 식물의 공격 범위에 들어서는 순간 즉시 죽으며, 어떤 공격 동작을 할 시간도 주어지지 않는다. 따라서 좀비가 어떤 식물이 차지한 위치로 들어가려는데 그 위치가 다른 식물의 공격 범위에 걸린다면, 좀비는 즉시 파괴되고 그 위치의 식물은 아무 피해도 입지 않는다. (이 설정에서 식물의 공격 범위에는 자기 자신의 위치가 포함되지 않는다. 그렇지 않으면 어떤 식물도 파괴할 수 없기 때문이다.)

좀비의 목표는 필드의 식물을 공격해 최대한 많은 에너지를 얻는 것이다. 각 단계에서 기존의 식물 하나를 골라 공격을 시작할 수 있다. 이 문제의 목표는 공격할 식물의 순서를 정해 좀비의 공격 계획을 설계함으로써 최종 에너지 수입을 최대한 크게 만드는 것이다.

첫째 줄에는 맵의 행 수와 열 수를 나타내는 두 정수 N과 M이 주어진다.

다음 N×M개의 줄에 격자의 각 위치에 있는 식물의 정보가 주어진다.

입력의 r×M+c+1번째 줄에 식물 Pr, c의 정보가 다음 형식으로 주어진다. 줄의 첫 번째 정수는 Score[Pr, c]이고, 두 번째 정수 w는 집합 Attack[Pr, c]의 원소 수이다. 같은 줄에 이어서 w쌍의 수 (r', c')가 주어지며, 각 쌍은 Pr, c의 공격 범위에 r'행 c'열 위치가 포함된다는 뜻이다.

좀비가 얻을 수 있는 최대 에너지 수입을 정수 하나로 출력한다. 참고로 공격을 하나도 시작하지 않을 수도 있으며, 이때 에너지 수입은 0이다.

• 1 ≤ N ≤ 20
• 1 ≤ M ≤ 30
• −10000 ≤ Score ≤ 10000.