BANK - Xếp hàng gửi tiền
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: duytoannguyenledh

Có n khách hàng đang xếp hàng gửi tiền vào ngân hàng X. Số tiền mà mỗi khách hàng muốn gửi lần lượt là a1, a2,..., an. Với mỗi người gửi tiền, thư ký ngân hàng phải tốn thời gian là 1 phút để hoàn tất thủ tục hồ sơ. Các khách hàng rất bận và họ chỉ có thể chờ trong một khoảng thời gian nào đó mà thôi, sau khoảng thời gian đó họ sẽ đi và không gửi tiền nữa. Thời gian mà các khách hàng có thể chờ lần lượt là t1, t2, ..., tn (tính theo phút). Chủ ngân hàng rất là tham lam, ông ta luôn muốn làm sao để có được nhiều tiền gửi nhất. Bạn hãy giúp thư ký lựa chọn thứ tự gửi tiền của các khách hàng sao cho số tiền ngân hàng có được là nhiều nhất (có thể phải chấp nhận từ chối một số khách hàng để đạt được mục đích).

Dữ liệu nhập:

- Dòng thứ nhất là số nguyên n (1 ≤ n ≤ 10.000)

- Trong n dòng tiếp theo, dòng thứ i gồm hai số nguyên ai và ti (1 ≤ ai ≤ 105, 0 ≤ ti ≤ 1.000).

Dữ liệu xuất:

- Là số nguyên xác định tổng số tiền nhiều nhất có thể thu được.

Ví dụ

  • input
    4
    10 1
    20 2
    5 2
    12 0
    output
    42
  • input
    3
    10 0
    20 1
    5 1
    output
    30
Back to Top