Chậm tiến độ

Công ty Bamboo hoạt động trong lĩnh vực xây dựng. Với rất nhiều mối quan hệ, công ty luôn kiếm được rất nhiều hợp đồng lớn nhỏ. Vì vậy, việc chậm tiến độ với các chủ đầu tư là điều thường xuyên xảy ra. Năm nay, công ty nhận được $n$ công trình. Công trình thứ $i$ bắt đầu nhận vào thời điểm $x_i$ và cần $t_i$ thời gian để toàn bộ lực lượng của công ty có thể thi công xong. Sau khi tính toán giá, các chủ đầu tư và lãnh đạo công ty đã thêm một điều khoản sẽ phạt $1$ USD với mỗi công trình trên một đơn vị thời gian chờ đợi (tính từ thời điểm nhận công trình tới khi thi công xong). Với lực lượng mỏng, trong một thời điểm, lực lượng công nhân của công ty chỉ có thể thi công một công trình duy nhất. Do đó, công ty thường xuyên bỏ dở công trình chuyển sang thi công công trình khác rồi sau đó có thể quay lại thi công tiếp nhằm tối đa lợi nhuận (tối thiểu tiền phạt) của công ty.

Yêu cầu: Hãy giúp ban lãnh đạo công ty xác định cách sắp xếp thi công để lượng tiền phạt công ty phải chịu là ít nhất. Biết việc thay đổi công trình và thời gian di chuyển là không đáng kể, không làm ảnh hưởng tới tổng thời gian để hoàn thành mỗi công trình.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $n$.
• Mỗi dòng trong $n$ dòng sau chứa $2$ số nguyên $x_i$ và $t_i$.

Dữ liệu ra

Một số nguyên: tổng tiền phạt nhỏ nhất công ty phải trả.

Ràng buộc

• $1\le n\le {10}^5$.
• $0\le x_i\le {10}^9$, $1\le t_i\le {10}^9$.

Subtasks

• Subtask 1 ($30\%$ số điểm): $n\le 100$, $t_1=t_2=\dots =t_n\le 100$; $x_i\le {10}^3$.
• Subtask 2 ($30\%$ số điểm): $n\le 100$, $x_i,t_i\le 1000$.
• Subtask 3 ($40\%$ số điểm): Không có ràng buộc gì thêm.

Ví dụ