"I love Big Black Cock" - huynhchiton981

BBC vừa mới tải về một trò chơi điện tử: Big Black Cock (Con gà trống khổng lồ màu đen). Trò chơi như sau: không gian trò chơi là một lưới ô vuông hai chiều kéo dài đến vô tận cả về chiều âm lẫn chiều dương. Gọi ô $(x,y)$ là giao của hàng thứ $x$ và cột thứ $y$ ($x$, $y$ có thể âm).

Có $n$ vật cản trên lưới tọa độ này. Người chơi có một con gà trống ở ô $(0,0)$. Gọi tọa độ hiện tại cua con gà trống là $(x,y)$. Gà trống có thể thực hiện $4$ thao tác:

1. Đi đến ô $(x-1,y)$.
2. Đi đến ô $(x+1,y)$.
3. Đi đến ô $(x,y-1)$.
4. Đi đến ô $(x,y+1)$.

Thao tác thứ $k$ có chi phí thực hiện $w_k$.

Tuy nhiên, đây không phải là một tựa game thông thường. Khi BBC thực hiện một thao tác, con gà trống sẽ đi theo hướng đó cho đến khi ô đứng trước ô của người chơi là một vật cản.

Dĩ nhiên, nếu không tồn tại vật cản khi người chơi thực hiện thao tác, con gà trống sẽ tiếp tục đi và đi, cho đến vô tận. Như vậy, có thể coi con gà đã chết và kết thúc trò chơi, BBC không muốn thế.

Ví dụ: người chơi đang ở ô $(0,0)$, và chỉ có một vật cản ở ô $(6,0)$. Khi đó, nếu BBC thực hiện thao tác $(2)$, con gà trống sẽ đi theo hướng đó cho đến khi bị vật cản chặn đường, như vậy BBC sẽ ở ô $(5,0)$. Nhưng nếu cậu thực hiện thao tác $(1)$, con gà trống sẽ chết và trò chơi sẽ kết thúc.

Có một chiếc chìa khóa ở ô $(x_0,y_0)$, và người chơi có thể lấy chìa khóa bằng cách đi qua ô này. Nhiệm vụ của người chơi là bằng những thao tác trên, hãy di chuyển sao cho tổng chi phí thực hiện các thao tác để từ $(0,0)$ đến lấy chìa khóa là thấp nhất. Hơn nữa, nhân vật không được chết sau khi lấy chìa khóa. (Cũng giống như việc bạn chơi bi 8 vậy, lỡ chốt bi đen rồi thì không được chết cái)

Sau khi chơi một hồi, BBC nhận ra trò chơi quá khó. Là một hacker chuyên nghiệp. BBC quyết định lập trình nên một công cụ giải trò chơi này. Và cậu ấy đã làm được (OMG!!!!) BBC thử thách bạn viết công cụ giải trò chơi này giống như anh ấy. Vì game quá dễ, nên sẽ có $Q$ trường hợp, trường hợp thử $t$ yêu cầu bạn giải quyết bài toán trên nếu chìa khóa được đặt tại $(x_t,y_t)$.

Input

• Dòng đầu tiên nhập vào số nguyên dương $T$ ($T\le 5$) là số lượng bộ dữ liệu.
• Dòng thứ hai nhập vào hai số nguyên dương $N,Q$ $(N,Q\le 50000)$, là số lượng vật cản và số lượng trường hợp.
• Dòng thứ ba nhập vào $4$ số nguyên dương $w_1,w_2,w_3,w_4$ ($w_1,w_2,w_3,w_4\le 10$).
• $N$ dòng tiếp theo, dòng thứ $i$ nhập vào hai số nguyên dương $x_i,y_i$ ($|x_i|,|y_i|\le 2500$) là tọa độ của vật cản thứ $i$.
• $Q$ dòng tiếp theo, dòng thứ $t$ nhập vào hai số nguyên dương $x_t,y_t$ ($|x_t|,|y_t|\le 2500$) là tọa độ chìa khóa trong trường hợp thứ $t$.
• Dữ liệu đầu vào đảm bảo tọa độ của các vật cản và chìa khóa là phân biệt và không tồn tại trường hợp chìa khóa trùng với vật cản, cũng như không có vật cản và chìa khóa nào có tọa độ $(0,0)$.

Output

• Với mỗi trường hợp, in ra tổng chi phí thực hiện thao tác thấp nhất để có thể lấy được chìa khóa. Nếu BBC không thể hoàn thành yêu cầu với chiếc bàn phím bị hỏng, hãy in $-1$.

Sample Input

1
4 6
1 2 3 4
0 -5
-5 -4
-4 5
1 4
0 -2
-2 -4
-4 0
-2 4
0 2
-2 0

Sample Output

3
4
8
10
13
-1

Giải thích test mẫu:

Vị trí của $N$ vật cản và $Q$ chìa khóa trong test mẫu nhìn giống như thế này:

• Để giải trường hợp $1$ (chìa khóa xanh dương), ta chỉ cần thực hiện thao tác $(3)$. Tổng chi phí là $3$.
• Để giải trường hợp $2$ (chìa khóa xám), ta thực hiện lần lượt thao tác $(3)$, $(1)$. Tổng chi phí là $4$.
• Không có cách nào để giải trường hợp $6$.

Scoring