Đêm khiêu vũ ở vũ trường

Trên mặt phẳng toạ độ có $n$ vũ công. Mỗi vũ công $i$ chỉ di chuyển bên trong phạm vi của mình, là hình tròn $C_i$ có tâm $(x_i,y_i)$ và bán kính $r_i$.

Các phạm vi có tính chất lồng nhau: với mọi cặp $(i,j)$, hoặc hai hình tròn $C_i$ và $C_j$ rời nhau, hoặc một hình tròn nằm hoàn toàn bên trong hình tròn kia. Đường biên của hai hình tròn có thể tiếp xúc nhau tại đúng một điểm, nhưng không có hai vũ công nào có phạm vi trùng khít.

Với một tập vũ công đang di chuyển, ta định nghĩa độ rộng rãi là diện tích phần mặt phẳng bị phủ bởi một số lẻ phạm vi trong tập đó.

Cả đêm được chia thành hai nửa: trước nửa đêm và sau nửa đêm. Mỗi vũ công di chuyển ở đúng một trong hai nửa (và ngồi nghỉ ở nửa còn lại). Độ rộng rãi của mỗi nửa được tính riêng, và tổng của chúng cần lớn nhất có thể.

Hãy tìm giá trị lớn nhất của tổng độ rộng rãi qua hai nửa đêm, khi ta được tự do chọn cách chia các vũ công vào hai nửa.

Dữ liệu vào

• Dòng đầu chứa số nguyên dương $n$ là số vũ công.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $x_i$, $y_i$, $r_i$ mô tả phạm vi hình tròn tâm $(x_i,y_i)$ bán kính $r_i$.

Dữ liệu ra

• Một số thực là tổng độ rộng rãi lớn nhất. Đáp án được chấp nhận nếu sai số tương đối hoặc tuyệt đối không vượt quá ${10}^{-9}$.

Ràng buộc

• $1\le n\le 1000$
• $-{10}^6\le x_i,y_i\le {10}^6$
• $1\le r_i\le {10}^6$
• Mọi cặp phạm vi rời nhau hoặc lồng nhau (biên có thể tiếp xúc tại một điểm).

Ví dụ