Trên một đường thẳng từ đỉnh núi xuống chân núi có trồng cây cổ thụ. Chính quyền địa phương quyết định chặt hạ chúng. Để không lãng phí gỗ, sau khi chặt cây phải vận chuyển đến xưởng cưa.
Gỗ chỉ có thể được vận chuyển xuống phía dưới chân núi. Tại chân núi đã có một xưởng cưa. Ngoài ra, hai xưởng cưa mới sẽ được xây dựng trên đường núi. Bạn phải quyết định vị trí xây dựng hai xưởng cưa này sao cho tổng chi phí vận chuyển là nhỏ nhất. Giả sử chi phí vận chuyển mỗi kg gỗ đi mỗi mét là 1 xu.
Nhiệm vụ của bạn là viết chương trình đọc vào số lượng cây, trọng lượng và vị trí của chúng, sau đó tính toán chi phí vận chuyển tối thiểu.
Dữ liệu:
Dòng đầu tiên chứa một số nguyên dương , biểu thị số lượng cây. Các cây được đánh số từ theo thứ tự từ đỉnh núi xuống chân núi.
dòng tiếp theo, mỗi dòng chứa hai số nguyên và . Lần lượt biểu thị trọng lượng (đơn vị kg) của cây thứ và khoảng cách từ cây thứ đến cây thứ . Số cuối cùng biểu thị khoảng cách từ cây thứ đến xưởng cưa ở chân núi.
Kết quả:
Xuất ra duy nhất một số, là chi phí vận chuyển nhỏ nhất.
Ví dụ:
Dữ liệu:
9
1 2
2 1
3 3
1 1
3 2
1 6
2 1
1 2
1 1
Kết quả:
26
Giới hạn:
Đối với 97 điểm dữ liệu: , đảm bảo tổng chi phí vận chuyển tất cả cây đến xưởng cưa ở chân núi nhỏ hơn . (Phần dữ liệu này là dữ liệu gốc).
Đối với 3 điểm dữ liệu còn lại: , đảm bảo mọi tính toán đều có thể thực hiện trong phạm vi số nguyên có dấu 64-bit.
