{"code":"concor","name":"Thu nhập thông tin (OLP 11 - 2018)","description":"Tại sa mạc Sahar có $S$ trạm rada mặt đất (đánh số từ 1 đến $S$) có chức năng thu-phát tín hiệu. Mỗi\r\ntrạm này thu tín hiệu từ vũ trụ rồi truyền phát những tín hiệu hữu ích thu được về trung tâm nghiên\r\ncứu vũ trụ *NAS*. Trạm $i$ đặt tại toạ độ ($x_i, y_i$), có bán kính truyền phát là $r_i$ và dung lượng tín hiệu\r\ncần truyền là $m_i$ (đơn vị tính là *TB-TeraByte*).\r\n\r\nCũng trên sa mạc *Sahar* này, NAS có đặt nhiều trạm làm việc cố định để phục vụ nhiệm vụ thu thập\r\nthông tin từ các trạm rada mặt đất nhờ các $UAV$ chuyên dụng (máy bay tự hành cỡ nhỏ tầm thấp).\r\nTrong phiên làm việc hôm nay, một *UAV* có tên **Concor** xuất phát từ trạm trung tâm có toạ độ (0,\r\n0) sẽ bay qua $N$ trạm làm việc (đánh số từ 1 đến $N$), lần lượt từ trạm 1 đến trạm $N$ rồi quay trở về\r\ntrạm trung tâm. Concor sẽ chỉ bay theo một đường thẳng giữa hai trạm làm việc liên tiếp. Trong quá\r\ntrình bay, bất kì khi nào khoảng cách giữa vị trí của Concor và vùng có tín hiệu truyền phát của một\r\ntrạm rada mặt đất nhỏ hơn hoặc bằng $D$, nó sẽ nhận được toàn bộ lượng tín hiệu cần truyền của trạm\r\nrada đó. Đặc biệt, nếu có trạm rada nào đó nằm trên hành trình của Concor thì Concor có giải pháp\r\nđể bay qua trạm đó một cách an toàn và thu được toàn bộ lượng tín hiệu tại đây. Concor chỉ thu\r\nnhận tín hiệu tại mỗi trạm rada không quá một lần.\r\n\r\n**Yêu cầu**: Cho trước thông tin về các trạm rada cũng như các trạm làm việc, hãy tính tổng dung\r\nlượng thông tin mà Concor thu nhận được trên hành trình.\r\n\r\n

Input

\r\n\r\n- Dòng đầu ghi 3 số nguyên $S, N, D$ lần lượt là: số trạm rada mặt đất, số trạm làm việc và\r\nkhoảng cách giới hạn mà Concor có thể nhận được tín hiệu từ các trạm rada ($1 \\le S, N \\le 2000; 1 \\le D \\le 50$).\r\n- $S$ dòng tiếp theo, dòng thứ $i$ chứa 4 số nguyên $x_i, y_i , r_i , m_i$ lần lượt là 2 toạ độ, bán kính\r\ntruyền phát và lượng thông tin cần truyền của trạm rada thứ $i$ như miêu tả phía trên ($1 \\le r_i \\le 100; 1 \\le m_i \\le 10000$).\r\n- $N$ dòng tiếp theo, dòng thứ $i$ trong các dòng này chứa 2 số nguyên $x_i, y_i$, là toạ độ của trạm\r\nlàm việc thứ $i$.\r\n\r\n*Các toạ độ $x_i, y_i$ của các trạm rada cũng như các trạm làm việc, là các số nguyên có giá trị tuyệt\r\nđối không vượt quá 5000. Các số thuộc cùng một dòng được ghi cách nhau bởi ít nhất một ký tự\r\ntrống (dấu cách). Dữ liệu đảm bảo không có hai trạm rada cũng như trạm làm việc nào có cùng\r\ntọa độ.*\r\n\r\n

Output

\r\n\r\n- Ghi ra duy nhất một số nguyên là tổng dung lượng\r\nthông tin (đơn vị tính là TB) mà Concor thu nhận được trên toàn bộ hành trình.\r\n\r\n

Scoring

\r\n\r\n- Subtask $1$ ($50\\%$ số điểm): $S, N \\le 500$.\r\n- Subtask $2$ ($50\\%$ số điểm): Không có ràng buộc gì thêm.\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 4 2 1\r\n 1 2 1 8\r\n 4 0 3 7\r\n 0 -2 1 6\r\n 7 -3 1 9\r\n 6 3\r\n 3 -1\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 21\r\n ```\r\n \r\n!!! question \"Test 2\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 7 4 1\r\n -3 0 1 5\r\n 1 2 1 8\r\n -2 5 1 9\r\n -2 -2 2 6\r\n 6 5 1 7\r\n 7 3 2 10\r\n 0 -3 1 4\r\n -2 3\r\n 1 4\r\n 4 4\r\n 3 -4\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 27\r\n ```","points":300.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}