Mô tả và yêu cầu

Tại của hàng pizza của Mr. Hải Dương có một điểm khác biệt với các cửa hàng khác,
nếu tại của hàng bình thường thì khách hàng đến trước sẽ được phục vụ trước, khách hàng
đến sau sẽ được phục vụ sau thì ở của hàng Pizza của Mr. Hải Dương sẽ phục vụ theo tiêu
chí thời gian đợi trung bình của khách hàng là nhỏ nhất, vì vậy Anh ta sẽ quyết định phục
vụ khách hàng nào trước chứ không phụ thuộc vào khách đến sớm hay muộn.
Mỗi loại bánh pizza khác nhau thì cần một khoảng thời gian khác nhau để làm bánh. Vì
chỉ có một lò nướng bánh nên trong thời gian nướng một chiếc bánh pizza này thì Anh ta
không thể nướng thêm chiếc bánh nào khác.
Ví dụ: Nếu cửa hàng có 3 khách đến vào các thời điểm 𝑡1 = 0, 𝑡2 = 1 và 𝑡3 = 2 và yêu
cầu 3 chiếc bánh pizza có thời gian làm bánh là 𝑙1 = 3,𝑙2 = 9,𝑙3 = 6. Nếu theo tiêu chí
khách đến trước được phục vụ trước thì thời gian chờ đợi của ba khách hàng lần lượt là
𝑞1 = 3, 𝑞2 = 11, 𝑞3 = 16. Như vậy thời gian chờ trung bình là (3 + 11 + 16)/3 = 10.
Đây không phải là phương án tối ưu theo tiêu chí thời gian chờ trung bình nhỏ nhất. Mr.
Hải Dương sẽ lựa chọn phục vụ theo thứ tự là khách 1, khách 3 và sau đó mới là khách 2.
Khi đó thời gian chờ của ba khách lần lượt là 𝑞1 = 3, 𝑞2 = 17, 𝑞3 = 7. Như vậy thời gian
chờ trung bình là (3 + 17 + 7)/3 = 9.
Yêu cầu: Bạn hãy giúp Mr. Hải Dương tính thời gian chờ trung bình nhỏ nhất. Chỉ cần in
ra phần nguyên của thời gian chờ trung bình nhỏ nhất.
Ghi chú:
- Thời gian chờ của một khách hàng là độ chênh lệch giữa hai thời điểm: thời điểm
khách hàng đến của hàng và thời điểm khách hàng rời cửa hàng;
- Mr. Hải Dương không biết trước các yêu cầu của khách hàng, tức là đến thời điểm
𝑡𝑖, khi khách hàng 𝑖 tới cửa hàng thì Mr. Hải Dương mới biết khách hàng 𝑖 yêu cầu
bánh pizza làm trong thời gian 𝑙𝑖.
Dữ liệu:
 Dòng đầu tiên chứa số nguyên dương 𝑛 (1 ≤ 𝑛 ≤ 105) là số khách hàng;
 𝑛 dòng tiếp theo, dòng thứ 𝑖 chứa hai số nguyên dương 𝑡𝑖, 𝑙𝑖 (0 ≤ 𝑡𝑖≤ 109, 1 ≤ 𝑙𝑖≤
109) mô tả khách hàng 𝑖 đến của hàng vào thời điểm 𝑡𝑖 và chiếc bánh khách hàng 𝑖
cần sẽ mất thời gian làm bánh là 𝑙𝑖.
Các số trên một dòng của input file được ghi cách nhau bởi dấu cách.
Kết quả: Ghi ra một số nguyên duy nhất là phần nguyên của thời gian chờ trung bình nhỏ
nhất.

Ví dụ

INPUT               OUTPUT                                Giải thích

   3                     8                    Thứ tự phục vụ là khách hàng 1, khách hàng
   0 3                                        3 và khách hàng 2.

   1 9                                        Thời gian chờ trung bình nhỏ nhất là: (3         +
                                              16 +  6)/3   = 25/3   =  8,33
   2 5

   4                     7                    Thứ tự phục vụ là khách hàng 1, khách hàng
   0 3                                        4, khách hàng 3 và khách hàng 2.

   20 1                                       Thời gian chờ trung bình nhỏ nhất là: (3         +
                                              1 +  17 +  7)/4  =  28/4   =  7
   1 9

   2 6