Giải phóng mặt bằng

Xem dạng PDF

Gửi bài giải


Điểm: 0,25 (OI)
Giới hạn thời gian: 0.9s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
HAOI 2008 - Day 1 - Author: Ngô Minh Ðức
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.