광물 채굴

이웃 항성계에 있는 행성을 개발하는 프로젝트가 진행 중이다. 광물을 캐기 위해 로봇 여러 묶음을 이 행성으로 보낼 계획이다.

광물을 캘 지역은 가로 $w$, 세로 $h$ 크기의 격자 사각형이다. 칸의 좌표는 $(1, 1)$부터 $(w, h)$까지이다. 일부 칸에는 전문가 기지가 있고, 로봇 묶음은 이 기지로 보내진다. 기지는 모두 $s$개이며, $i$번째 기지는 $(x_i, y_i)$ 칸에 있다.

$j$번째 묶음은 기지 $b_j$로 보내지며, 로봇 $n_j$대로 이루어져 있다. 묶음의 각 로봇은 이동 능력 $m_j$를 가진다. 묶음이 기지에 도착하면 각 로봇은 기지에서 출발해 행성 표면의 어떤 칸까지 이동한다. 이동 능력이 $m$인 로봇은 인접한 여덟 칸 중 하나로 최대 $m$번 이동할 수 있다(그림 1 참고).

모든 묶음의 로봇을 배치하면 로봇을 활성화하고, 로봇은 광물 채굴을 시작한다. 이동 중에는 한 칸에 로봇이 여러 대 있어도 된다. 그러나 활성화된 뒤에는 어떤 칸에도 로봇이 $q$대를 넘으면 안 된다.

관리팀은 순서대로 보낼 수 있는 $t$개의 로봇 묶음 정보를 받았다. 모든 묶음을 보낸 뒤에는 이동 능력에 제한이 있어서, 어느 칸에도 $q$대를 넘지 않게 로봇을 배치하지 못할 수도 있다. 그래서 관리팀은 처음 $k$개 묶음($0 \le k \le t$)을 골라 해당 기지로 전부 보낸다. $k < t$이면 그다음 묶음, 즉 $(k+1)$번째 묶음의 로봇 $n_{k+1}$대 중 $z$대를 추가로 받는다($0 \le z < n_{k+1}$).

관리팀은 $k$를 최대화하고, 그다음 $z$를 최대화한다.

첫 줄에 $w$, $h$, $s$, $q$가 주어진다. $1 \le w, h \le 10^5$, $1 \le s \le 4$, $1 \le q \le 100$이다. 이어지는 $s$개 줄에는 기지의 좌표 $x_i$, $y_i$가 주어진다($1 \le x_i \le w$, $1 \le y_i \le h$). 다음 줄에는 묶음 수 $t$가 주어진다($1 \le t \le 100$). 이어지는 $t$개 줄에는 $b_j$, $n_j$, $m_j$가 주어진다($1 \le b_j \le s$, $1 \le n_j \le w \cdot h \cdot q$, $0 \le m_j < \max(w, h)$).

예제에서는 첫 번째 묶음 전체를 받고, 두 번째 묶음에서 로봇 7대를 추가로 받는다. 그림 2는 이 로봇들을 칸마다 한 대 이하가 되도록 배치한 모습이다. 기지는 원으로 표시했다. 기지 1에서 온 로봇이 있는 칸은 세로 빗금, 기지 2에서 온 로봇이 있는 칸은 회색으로 표시했다.