선물이 넘쳐흘러

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

$B \times B$ 격자 모양 공장에는 안쪽 가장자리를 따라 놓인 ⊐ 모양의 컨베이어 벨트가 있다. 벨트의 시작 지점은 공장의 맨 위 가장 왼쪽 칸이고, 끝 지점은 맨 아래 가장 왼쪽 칸이다. 벨트는 1초마다 시작 지점에서 ⊐ 모양을 따라 끝 지점을 향해 한 칸씩 움직인다. 모든 선물은 이 벨트로 운반되며, 벨트가 한 칸 움직일 때마다 시작 지점에 선물이 하나씩 놓인다. 처음에 벨트 위에는 아무것도 없다.

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

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

위 그림의 예를 보자. 공장 크기는 $5 \times 5$, 포장할 선물은 6개, 직원은 3명이다. 직원1의 위치는 $(1, 1)$이고 포장에 $T_1 = 3$초가 걸린다. 직원2는 $(1, 3)$이고 $T_2 = 2$이다. 직원3은 $(3, 2)$이고 $T_3 = 1$이다. $(r, c)$는 행과 열 번호이며 $(0, 0)$부터 센다. 이 경우 포장할 수 있는 선물은 총 6개이다.

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

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

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

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