eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Путівки

Путівки

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Туристична фірма не встигла через великі морози продати n (n < 15) путівок на гірськолижні бази, термін дії яких вже настав. Щоб зменшити втрати, було вирішено з 1 лютого всі такі путівки, яким залишилось d_k (d_k ≤ 30) днів, продавати за номінальною вартістю – по c_k (c_k ≤ 100) грн за день лише за ті дні, які залишились з дня продажу (k = 1..n).

На яку найбільшу суму можна реалізувати ці путівки, якщо кожного дня продавати по одній путівці?

Вхідні дані

Перший рядок містить кількість путівок n. Кожний з наступнихn рядків містить два числа – кількість днів d_k і вартість дня c_k.

Вихідні дані

Найбільша сума прибутку.

Приклад

Вхідні дані #10
4
2 37
3 45
1 46
4 30
Вихідні дані #10
232