17259번 - 선물이 넘쳐흘러

파티가 끝난 다음 날, 욱제는 파티에 왔던 팬들이 놓고 간 5조5억 개의 선물을 발견했다! 이에 감동한 욱제는 자신도 팬들에게 선물을 주기로 했다. 욱제는 귀찮아서 받은 선물을 포장만 바꿔서 주기로 했다. 욱제는 귀찮아서 선물을 조금 팔고 그 돈으로 선물 포장 공장을 차려 버렸다.

B×B 크기의 격자 모양 공장에는 안쪽 가장자리를 따라 위치한 ⊐ 모양의 컨베이어 벨트가 있다. 벨트의 시작 지점은 공장의 맨 위 가장 왼쪽 지점이고, 벨트의 끝 지점은 공장의 맨 아래 가장 왼쪽 지점이다. 벨트는 1초 간격으로 시작 지점에서 ⊐ 모양을 따라 끝 지점을 향해 한 칸씩 움직인다. 모든 선물은 이 벨트를 통해 운반되고, 벨트가 한 칸 움직이면 시작 지점에 선물이 하나씩 놓인다. 최초에 벨트 위에는 아무것도 없다.

욱제는 공장에서 M개의 선물을 포장하기 위해 N명의 직원을 고용했다. 직원들은 벨트와 인접한 칸에서만 일하며, 한 칸에는 한 명 이하의 사람이 위치한다. i번째 직원은 선물 하나를 포장하는 데 T_i초가 걸린다. 직원들은 성실해서 포장하는 중이 아니라면 항상 인접한 선물이 있는지 살핀다. 직원들은 상하좌우의 컨테이너 벨트 위에 있는 선물 중 하나를 포장할 수 있다. 만약 인접한 선물이 2개 이상이라면, 벨트 위에 더 오래 올려져 있던 선물을 포장한다. 선물 M개가 모두 시작 지점에 오르고 나면, 시작 지점에는 더 이상 새로운 선물이 놓이지 않는다.

욱제는 악덕사장이라서 직원들이 쉬는 걸 하락하지 않는다. 그래서 포장하는 중이 아닌 직원들은 벨트가 움직이고 선물이 인접한 칸에 놓이면 바로 포장을 시작한다. 포장할 때는 선물을 벨트 위에서 바로 내리기 때문에 뒤따라 오는 선물들은 항상 막힘 없이 벨트 위를 지나갈 수 있다. 포장이 끝나면 바로 다른 선물을 포장할 수 있고, 포장되지 않은 선물이 벨트의 끝 지점을 지나면 그 선물은 벨트에서 떨어져 폐기된다.

위 그림의 예를 들어보자. 공장의 크기가 5×5이고, 포장할 선물이 6개, 직원이 3명이다. 직원1의 위치는 (1, 1)이고 선물 포장에 T₁=3초가 걸린다. 직원2는 (1, 3), T₂=2이다. 직원3은 (3, 2), T₃=1이다. (r, c)는 행과 열 번호이며 (0, 0)을 시작으로 한다. 이 경우 포장할 수 있는 선물의 총 개수는 6개이다.

욱제는 몇 개의 선물을 팬들에게 전달할 수 있을까?

첫째 줄에 공장의 크기 B (4 ≤ B ≤ 100), 직원의 수 N (1 ≤ N ≤ (3B - 6)), 선물의 개수 M (1 ≤ M ≤ 100)이 주어진다.

둘째 줄부터 N개의 줄에 걸쳐, 각 줄마다 i번 직원의 위치 r_i, c_i (1 ≤ r_i ≤ (B-2), 0 ≤ c_i ≤ (B-2))와 선물 하나를 포장하는데 걸린 시간 T_i (1 ≤ T_i ≤ 10)가 주어진다.

욱제가 얻을 수 있는 포장된 선물의 총 개수를 출력한다.