16077번 - Монгол ардын үлгэр 다국어

Хайгуулч Дондог түүний туслах Индиана Жонс ээлжит хайгуулаар N ширхэг эрдэнэсийн чулуу олов. Чулуу бүр Ci үнэтэй ба Ti жинтэй. Дондог эрдэнэсээ хуваах сонирхолтой арга бодож олсон. Тэрээр Жонсод өгсөн чулуунуудын нийлбэр жингээс ихгүй тооны ширхэг чулууг өөртөө авч байхаар хуваадаг. Жишээ нь Жонс-д 1, 2, 1 гэсэн жинтэй 3 чулуу байгаа бол Дондог 4 хүртэлх ширхэг чулууг өөртөө авч чадна. Дондогийн авах чулуунуудын үнийн нийлбэрийг хамгийн их байлгахад тусална уу.

Эхний мөрөнд эрдэнэсийн тоо N(1 ≤ N ≤ 2000) өгөгдөнө. Дараагийн N мөр бүрт T_i, C_i (1 ≤ T_i ≤ 2000, 1 ≤ C_i ≤10⁹) хос тоо өгөгдөх ба тус бүр i-дугаар чулууны жин, үнийг илэрхийлнэ.

Нэг мөрөнд Дондогийн авч чадах чулуунуудын хамгийн их үнийн дүнг хэвлэнэ.

Жишээ нь дээр Жонс-д сүүлийн хоёр чулууг өгч өөрөө сүүлийн хоёр чулууны нийлбэртэй тэнцүү байх тооны чулууг авсан.