Lì Xì

Xem PDF
Tác giả:
corona
Dạng bài
Điểm: 300 (p) Thời gian: 1.1s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Nhân dịp Tết, ba bé Bo chuẩn bị \(n\) túi lì xì cho bé Bo. Trong túi thứ \(i\) có số tiền là \(a_i\) và một số nguyên \(b_i\) \((b_i ≥ 0)\). Nếu \(b_i > 0\) thì bé Bo được phép chọn thêm \(b_i\) túi lì xì khác. Việc chọn thêm này là tích lũy. Đầu tiên, bé Bo chọn một túi bất kỳ, sau đó giả sử bé Bo đang có tổng số tiền là \(A\) và số túi được phép chọn thêm là \(B\) \((B > 0)\), nếu bé Bo chọn thêm túi thứ \(i\) thì tổng số tiền là \(A + a_i\) và tổng số túi được chọn thêm là \(B -1 + b_i\). Cứ như vậy cho đến khi không được phép chọn thêm \((B=0)\) hoặc đã chọn hết \(n\) túi.

Yêu cầu: Bạn hãy giúp bé Bo xác định thứ tự chọn túi sao cho tổng số tiền bé có được là lớn nhất nhé.

Input

  • Dòng đầu tiên là số nguyên \(n\) \((1 \leq n \leq 100)\).

  • Trong \(n\) dòng tiếp theo, dòng thứ \(i\) gồm \(2\) số nguyên \(a_i\) và \(b_i\) cách nhau một khoảng trắng \((1 \leq a_i \leq 100, 0 \leq b_i \leq 100)\).

Output

  • Là số nguyên xác định số tiền nhiều nhất mà bé Bo có được.

Example

Test 1

Input 
3
1 0
2 0
0 2
Output 
3

Test 2

Input 
5
0 0
2 0
2 0
3 0
5 1
Output 
8
Note

  • Trong test 1, do chỉ chọn được 1 túi nên chọn túi có số tiền nhiều nhất là 2.

  • Trong test 2, đầu tiên chọn túi 3, sau đó chọn túi 1 và tiếp theo là túi 2.

Bình luận


  • -3
    Toilaaibanbietko7A4    10:39 a.m. 12 Tháng 7, 2020

    Ủa có ăn phải hột vịt lộn khi ra đề không dzậy?
    "Trong test 1, do chỉ chọn được 1 túi nên chọn túi có số tiền nhiều nhất là 2."
    Thế sao test 1 kết quả là 3? Ra giải thích sai à? hí hí!


    • 1
      nhinhinhdoanten99    9:05 p.m. 24 Tháng 7, 2020

      Hình như lúc đầu được bốc 1 bao lì xì mà bạn?
      Và khi bốc bao thứ 3 thì được thêm 2 cơ hội.


      • 1
        Toilaaibanbietko7A4    10:42 a.m. 25 Tháng 7, 2020 ← đã chỉnh sửa

        Biết rồi, nhưng nhìn kĩ đi: có số tiền nhiều nhất là 2 . Mà phải chọn túi 3 mới có 2 lần chọn tiếp theo chứ


        • 1
          stupidloc4    1:40 p.m. 25 Tháng 7, 2020

          bài gốc là có 3 test. người làm đề này copy lộn giải thích test khác


          • 1
            lagiahuy    6:33 p.m. 8 Tháng 10, 2021

            chắc ghép nhầm test với nhầm giải thích ấy, Trong test 2, đầu tiên chọn túi 3, sau đó chọn túi 1 và tiếp theo là túi 2.

            3
1 0
2 0
0 2

            • 0
              Toilaaibanbietko7A4    10:27 a.m. 26 Tháng 7, 2020

              Oh! Tks

        4 bình luận nữa