HAOI 2008 Online

Chính quyền thành phố KN đang tiến hành mở thêm một tuyến đường mới trong thành phố. Chính quyền có bản đồ tọa độ của N hộ dân trong khu vực tuyến đường có thể đi qua. Tuyến đường là một đường thẳng đi qua tọa độ các hộ dân. Các hộ dân được đánh số từ 1 đến N; hộ dân thứ i có diện tích sử dụng là s_i (m²). Nếu tuyến đường đi ngang qua hộ dân thứ i, chính quyền cần phải đền bù cho hộ dân này s_i²+5 (đồng) tiền giải phóng mặt bằng. Hỏi chính quyền cần phải đền bù nhiều nhất bao nhiêu tiền khi xây dựng tuyến đường?

Dữ liệu

• Dòng 1: một số nguyên N là số hộ dân (1 ≤ N ≤ 1500).
• Dòng thứ i trong N dòng tiếp theo chứa 3 số nguyên x_i, y_i, s_i cho biết tọa độ và diện tích của hộ dân thứ i (-50 ≤ x_i, y_i ≤ 50, 30 ≤ s_i ≤ 500).

Kết quả

In ra một số duy nhất là số tiền nhiều nhất chính quyền phải đền bù khi xây dựng tuyến đường.

Ví dụ

Dữ liệu
5
0 0 1
1 1 2
2 2 4
0 1 5
1 0 3

Kết quả	
51