Ngôi làng X đang phải trải qua đợt hạn hán nghiêm trọng nhất trong lịch sử. Để đối phó với nạn hạn hán, các bô lão đã quyết định sẽ phân phối lại lượng nước tại các giếng nước trong ngôi làng tại các điểm dân cư, nhằm đảm bảo cung cấp đầy đủ lượng nước cho quá trình sinh hoạt của người dân.

Có ~n~ điểm dân cư trong ngôi làng, điểm dân cư thứ ~i~ có nằm ở tọa độ ~(x_i, y_i)~. Tại mỗi điểm dân cư đều có một giếng để có thể lưu trữ nước sạch, lượng nước hiện tại trong giếng ở điểm dân cư thứ ~i~ là ~a_i~ lít.

Các bô lão có thể dùng xe kéo để di chuyển nước giữa hai điểm dân cư bất kì. Tuy nhiên, do thời tiết nắng nóng kéo dài nên lượng nước sẽ bị hao hụt một lượng lít nước đúng bằng khoảng cách Euclide giữa hai điểm dân cư trong quá trình vận chuyển. Cụ thể, nếu vận chuyển ~x~ lít nước từ điểm dân cư ~i~ đến điểm dân cư ~j~ thì lượng nước mà thành phố ~j~ nhận được sẽ là ~max(0, x - d_{i,j})~ lít với ~d_{i,j}~ là khoảng cách Euclide giữa hai điểm dân cư ~i~ và ~j~.

Các bô lão mong muốn tìm cách vận chuyển nước sao cho lượng nước tại giếng ít nước nhất là nhiều nhất có thể.

Yêu cầu: Hãy giúp các bô lão tìm ra lượng nước trên.

Input

• Dòng đầu tiên chứa một số nguyên ~n~ (~1 \le n \le 14~) là số điểm dân cư.
• Dòng thứ ~i~ trong ~n~ dòng tiếp theo gồm ba số nguyên ~x_i, y_i, a_i~ (~0 \le x_i, y_i, a_i \le 10^9~) là tọa độ và lượng nước trong giếng của điểm dân cư thứ ~i~. Dữ liệu vào đảm bảo không có hai điểm dân cư nào có cùng tọa độ.

Output

• Gồm một số thực duy nhất là lượng nước lớn nhất có thể tại giếng ít nước nhất với cách vận chuyển nước tối ưu. Đáp án của bạn được xem là đúng nếu chênh lệch tương đối hoặc tuyệt đối so với đáp án của ban giám khảo không vượt quá ~10^{-6}~.