Багатьом вiдома класична задача про рюкзак. У цiй задачi ми маємо \(N\) предметiв iз об'ємом \(C_i\) та вартiстю \(V_i\) i нам треба упакувати у рюкзак предмети на максимальну вартiсть i при цьому не перевищити об'єм рюкзака. На жаль наш рюкзак порвався i треба купити новий. Але новий рюкзак ми хочемо мати такого розмiру, щоб предмети, якi ми туди впакуємо, мали би максимальну сумарну вартiсть. Знайдiть мiнiмальний об'єм рюкзака, що задовольняє описанi вимоги.
Формат вхiдних даних
Перший рядок вхiдного потоку мiстить цiле число \(N\) , де \(1 ⩽ N ⩽ 10^5\) .
Наступнi \(N\) рядкiв мiстять по два цiлих числа - об'єм предмета та його вартiсть: \(C_i\) , \(V_i\) , де \(0 ⩽ C_i ⩽ 10^5\) , - \(10^9 ⩽ V_i ⩽ 10^9 \)
Формат вихiдних даних
У вихiдний потiк вивести мiнiмальний об'єм рюкзака, який помiстить предмети на максимальну суму
Приклад вхідних даних
2
1 0
9 2
Приклад вихідних даних
9
Приклад вхідних даних
1
1 -9000
Приклад вихідних даних
0
Коментарі