광물 매장지

당신은 외계 채굴 회사에서 신호 처리를 맡고 있다. 당신의 우주선이 소행성에 접근하고 있다. 예비 스캔 결과 소행성에 $k$개의 광물 매장지가 있는 것으로 나타났지만, 정확한 위치는 알려지지 않았다.

소행성 표면은 정수 좌표로 이루어진 격자로 볼 수 있다. $i$번째 매장지는 정수 좌표 $(x_i, y_i)$에 있으며, $-b \le x_i \le b$, $-b \le y_i \le b$를 만족한다. 여기서 $b$는 초기 스캔의 크기에 해당하는 정수이다.

정확한 위치를 알아내기 위해 소행성 표면으로 탐사선을 보낼 수 있다. 탐사선은 여러 대씩 묶어 한꺼번에 보내며, 이를 웨이브라고 한다.

좌표 $(s_j, t_j)$로 탐사선 $d$대로 이루어진 웨이브를 보낸다고 하자($1 \le j \le d$). 탐사선은 도착하면 $k$개의 매장지 각각까지의 맨해튼 거리를 측정해 우주선으로 돌려보낸다. 모든 데이터 패킷은 같은 시각에 도착하므로, 어느 탐사선이 어떤 거리를 돌려보냈는지는 구별할 수 없다. 따라서 한 웨이브에서 돌아오는 값은 다음과 같은 $k \cdot d$개의 정수 거리이다.

$|x_i - s_j| + |y_i - t_j| \qquad \text{for all } i \in \{1, \ldots, k\} \text{ and } j \in \{1, \ldots, d\}.$

소행성 표면으로 보내는 탐사 웨이브의 횟수를 최소화해야 한다.

항상 $1 \leq b \leq 10^8$, $1 \leq k \leq 20$, $2 \leq w \leq 10^4$이다.