Trên mặt biển có ~n~ hòn đảo. Có thể xem mặt biển là một mặt phẳng còn các hòn đảo là các điểm nằm tại các tọa độ ~(x_1, y_1)~, ~(x_2, y_2)~, ..., ~(x_n, y_n)~, nghĩa là đảo thứ ~i~ cách gốc tọa độ ~x_i~ mét theo trục hoành, ~y_i~ mét theo trục tung. Ban đầu mỗi hòn đảo là một hình vuông có chiều dài cạnh là 2 mét (tâm hình vuông là tọa độ các hòn đảo). Sau đó mỗi tháng tùy theo lượng phù sa nhiều hay ít mà mỗi hòn đảo được bồi đắp mở rộng cả bốn hướng mỗi hướng thêm 1 mét (phù sa ít) hay 2 mét (phù sa nhiều) để tạo thành hình vuông lớn hơn. Trong một tháng các hòn đảo đều được bồi đắp giống nhau (cùng 1 mét hoặc cùng 2 mét).

Giả sử nếu quá trình bồi đắp xảy ra trong ~k~ tháng, bạn hãy tính xem có sự va chạm giữa các hòn đảo hay không (ít nhất 2 đảo chạm nhau) và sự va chạm đó xảy ra vào tháng nào. (Nếu sau một tháng nào đó, cạnh hai đảo chỉ mới chạm mép vào nhau, hoặc 2 đỉnh chạm nhau thì cũng xem như tháng đó xảy ra sự va chạm).

Input

• Dòng đầu chứa số nguyên ~T~ là số bộ dữ liệu (~1 ≤ T ≤ 100~).
• Mỗi bộ dữ liệu gồm:
  • Dòng đầu tiên chứa 2 số nguyên ~n~ và ~k~ là số hòn đảo và số tháng bồi đắp, hai số cách nhau một khoảng trắng (~2 ≤ n ≤ 200, 1 ≤ k ≤ 100.000~).
  • Trong ~n~ dòng tiếp theo, tại dòng thứ ~i~ gồm 2 số ~x_i~ và ~y_i~ là tọa độ các hòn đảo, hai số cách nhau một khoảng trắng (~-10^9 ≤ x_i, y_i ≤ 10^9~).
  • Trong dòng tiếp theo là một dãy ~k~ ký tự ứng với ~k~ tháng bồi đắp, nếu đó là ký tự '1' thì tháng đó mở rộng 1 mét, nếu đó là ký tự '2' thì tháng đó mở rộng 2 mét, ngoài ra không có ký tự khác.

Output

• Với mỗi bộ dữ liệu, in ra kết quả trên một dòng:
  • Nếu sau ~k~ tháng không có 2 đảo nào chạm nhau, in ra ~-1~.
  • Nếu có đảo chạm nhau, in ra số nguyên là tháng mà sau khi bồi đắp thì bắt đầu xảy ra va chạm.

Sample Test

Input 1

2 4
1 0
7 0
1122

Output 1

2

Input 2

2 5
1 1
13 13
21112

Output 2

4

Input 3

2 7
1 0
100 1
1121122

Output 3

-1