Trong một lần đi ngao du sơn thủy, GS. X không may lạc vào vương quốc của những cửa hàng trà sữa. Vị giáo sư mặc dù rất thích uống trà sữa nhưng vẫn muốn tìm cách thóa ra khỏi đó còn tiếp tục đi quảng cáo kiếm tiền mua trà...

Có thể coi vương quốc trà sữa thực sự là không gian 3D, để thoát ra khỏi vương quốc này, trước hết GS. X cần nạp năng lượng cho mình bằng việc ... uống trà sữa. Có ~n~ cửa hàng, cửa hàng trà sữa thứ ~i~ đặt tại điểm ~(x_i, y_i, z_i)~ và có thể bán lượng trà sữa tối đa là ~e_i~.

GS. X đang đứng tại điểm ~x_s, y_s, z_s)~. Các cửa hàng trà sữa đều cung cấp loại ống hút dài vô tận, giúp GS. X có thể đứng từ vị trí hiện tại hút trà sữa từ mọi cửa hàng (hút hết lượng trà sữa của cửa hàng đó) mà không cần phải di chuyển. Tất nhiên, ống hút sẽ được đặt theo đoạn thẳng nối giữa vị trí của GS. X và quán trà sữa.

Tuy nhiên, việc hút trà sữa của GS không thực sự dễ dàng như vậy. Do đang là mùa giáng sinh nên các cửa hàng có treo các quả cầu giáng sinh ở khắp nơi. Theo quan sát của GS, có ~m~ quả cầu rỗng đang được treo, quả cầu thứ ~i~ có bán kính ~r_i~ và có tâm đặt tại ~(x_i, y_i, z_i)~. GS. X sẽ không thể hút trà sữa từ một quán nếu đoạn thẳng nút vị trí của GS tới quán đó bị chắn bởi ít nhất 1 quả cầu.

Vì muốn bán được nhiều trà sữa nên nhân viên các cửa hàng quyết định sẽ dọn đi ~k~ quả cầu. Bạn hãy tính lượng trà sữa lớn nhất GS. X có thể hút được từ vị trí của mình nếu đã dọn đi ~k~ quả cầu.

Input

• Dòng đầu tiên gồm 3 số ~m, n, k (1 \le m \le 2000, 1 \le n \le 15, k \le m)~
• ~m~ dòng tiếp theo, dòng thứ ~i~ gồm 4 số ~x_i, y_i, z_i~ và ~r_i~ mô tả tọa độ tâm và bán kính của quả cầu thứ ~i~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ gồm 4 số ~x_i, y_i, z_i~ và ~e_i~ thể hiện tọa độ và lượng trà sữa của cửa hàng thứ ~i~.
• Dòng cuối cùng gồm 3 số ~x_s, y_s, z_s~ mô tả vị trí GS. X đang đứng.

Lưu ý:

• Tất cả các tọa độ và bán kính đều có giá trị tuyệt đối không quá 500; ~1 \le e_i \le 80000~. Tọa độ GS. X đang đưgns và tọa độ cửa hàng trà sữa có thể nằm trong hoặc nằm ngoài quả cầu.
• Nếu tọa độ của GS. X hoặc cửa hàng nằm trên biên của quả cầu thì được coi là nằm trong quả cầu.
• Nếu đường thẳng nối cửa hàng và vị trí GS. X đi qua biên của quả cầu thì quả cầu cũng cần phải phá bỏ.

Output

• Một dòng duy nhất, ghi tổng lượng năng lượng lớn nhất có thể thu được.

Sample

Input #1

12 5 4
0 10 0 1
1 5 0 2
1 4 0 2
0 0 0 2
10 0 0 1
3 -1 0 2
5 -1 0 2
10 10 0 15
0 -10 0 1
10 -10 0 1
-10 -10 0 1
10 10 0 1
0 10 0 240
10 0 0 200
10 -2 0 52
-10 0 0 100
1 1 0 2
0 0 0

Output #1

254

Input #2

1 2 0
0 0 0 1
-1 0 0 5
2 0 0 100
1 0 0

Output #2

5

Hint

Giải thích test #1:

Problem source: PreVNOI Ⅶ (NINH BÌNH 2017)