Công ty L có một số nhà máy trên núi. Do ngọn núi này nằm trong khu vực nội địa cao nguyên (khô hạn ít mưa), công ty L thường để sản phẩm trực tiếp ngoài trời để tiết kiệm chi phí. Đột nhiên một ngày, chủ tịch L nhận được điện thoại từ cơ quan khí tượng thông báo rằng ba ngày sau sẽ có một trận mưa lớn, vì vậy ông quyết định khẩn cấp xây dựng một số kho hàng tại một số nhà máy để tránh sản phẩm bị hỏng do mưa.
Công ty L có nhà máy trên núi. Nhà máy ở trên đỉnh núi, nhà máy ở chân núi.
Do địa hình khác nhau, chi phí xây dựng kho hàng tại các nhà máy khác nhau cũng có thể khác nhau. Nhà máy hiện có sản phẩm thành phẩm, chi phí xây dựng kho hàng tại nhà máy này là . Đối với các nhà máy không xây dựng kho hàng, sản phẩm của chúng phải được vận chuyển đến các kho hàng khác để lưu trữ. Vì bộ phận bán hàng của công ty L đặt tại nhà máy ở chân núi, nên sản phẩm chỉ có thể vận chuyển xuống núi (nghĩa là chỉ có thể vận chuyển đến nhà máy có số hiệu lớn hơn). Tất nhiên, việc vận chuyển sản phẩm cũng tốn chi phí, giả sử chi phí vận chuyển 1 sản phẩm đi 1 đơn vị khoảng cách là 1. Giả sử sức chứa của các kho hàng được xây dựng đều đủ lớn để chứa tất cả sản phẩm.
Đã biết:
Khoảng cách từ nhà máy đến nhà máy là (trong đó );
Số lượng thành phẩm hiện có tại nhà máy là ;
Chi phí xây dựng kho hàng tại nhà máy là .
Hãy giúp công ty L tìm một phương án xây dựng kho hàng sao cho tổng chi phí (chi phí xây dựng + chi phí vận chuyển) là nhỏ nhất.
Dữ liệu:
Dòng đầu tiên chứa một số nguyên , biểu thị số lượng nhà máy.
dòng tiếp theo, mỗi dòng chứa ba số nguyên , ý nghĩa như đã mô tả.
Kết quả:
Chứa duy nhất một số nguyên, là chi phí của phương án tối ưu tìm được.
Ví dụ:
Dữ liệu:
3
0 5 10
5 3 100
9 6 10
Kết quả:
32
Giới hạn: .
Đảm bảo tất cả đều nằm trong phạm vi int.
Đảm bảo kết quả tính toán trung gian không vượt quá phạm vi long long.
