#247. FLOWERS - Phá hoại vườn hoa

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Tại trang trại của HD có N con chó dữ, trong một ngày mưa, tất cả đàn chó dữ đã xổng chuồng và xông ra phá hoại vườn hoa xinh đẹp của HD. Mỗi con cho có đặc điểm sau:

  • Di chuyển từ vườn hoa về chuồng mất t (s);
  • Sau 1 s sẽ phát nát d bông hoa.

HD trong một lần, chỉ có thể dắt một con chó về chuồng, tổng thời gian di chuyển là 2\times t (s) (dắt chó về và di chuyển quay lại vườn hoa).

Bạn hãy tính xem, ít nhất bao nhiêu bông hoa bị phá nát?

Dữ liệu vào:

  • Dòng đầu chứa số nguyên dươn N\ (1≤N≤10^5) ;
  • N dòng sau, dòng thứ i gồm hai số t d tương ứng với đặc điểm của con cho i . (1≤t≤2\times 10^6; 1≤d≤100) .

Dữ liệu ra:

  • Một số duy nhất là số bông hoa ít nhất bị phá hủy.

Ví dụ:

Dữ liệu vào:
6
3 1
2 5
2 3
3 2
4 1
1 6
Dữ liệu ra:
86

Giải thích: Dắt chó theo thứ tự: 6, 2, 3, 4, 1, 5 .