Бізнес-план деякої компанії містить ~N~ мініпроєктів, які при вчасному виконанні принесуть прибуток. І-й проєкт дасть прибуток ~Q_i~, якщо його виконати до часу ~T_i~.

Напишіть програму, яка визначить максимальний прибуток компанії при оптимальному виконанні мініпроєктів. Ваша програма починає працювати при t=0.

Input

Перший рядок містить ~N~ (~1 \le N \le 10000~)

Наступні ~N~ рядків містять прибуток та час завершення для кожного мініпроєкту: ~Q_i~, ~T_i~ (~1 \le Q_i \le 1000, 1 \le T_i \le 10000~)

Output

Вивести одне число - максимальний прибудок від реалізації мініпроектів.

Scoring

• при ~N \le 30~ - 21 бал,
• при ~N \le 3 000~ - 27 балів,
• при ~N \le 10 000~ - 52 бали

Sample Input 1

4
10 3
7 5
8 1
2 1

Sample Output 1

25

Notes

Спочатку реалізовуємо проєкт 3(4-й ігноруємо). Потім виконуємо проєкти 1 та 2.