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^{2})~. 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} ^ 2 + 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?

Input

• Dòng ~1~: một số nguyên ~N~ là số hộ dân ~(1 \leq N \leq 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 \leq x_{i}~, ~y_{i} \leq 50~, ~30 \leq s_{i} \leq 500)~.

Output

• 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.

Sample Input

5
0 0 1
1 1 2
2 2 4
0 1 5
1 0 3

Sample Output

51