Бавимося в CS
Обмеження: 2 сек., 256 МіБ
Сьогодні великий день. Уперше в історії збірна algotester пройшла в фінал турніру з CS: GO. І ось найважливіший раунд — кілька секунд до початку, але в цей момент команда розуміє, що в них немає стратегії для перемоги.
Вони знають, що можна купити якийсь набір зброї, кожен з яких коштує \(w_i\) грошей та дає \(a_i\) впевненості в перемозі. Кожну зброю можна купити лише 1 раз! На жаль, минулий раунд вони програли, тому кількість грошей у них обмежена й дорівнює \(m\).
Спливають останні секунди, і капітан згадав про студентів бурситету, що можуть помогти вибрати правильну стратегію. Він просить вас написати програму, що скаже, яку максимальну впевненість можна отримати при певному закупі.
Вхідні дані
У першому рядку задано два цілих числа \(n\) та \(m\) — кількість наборів зброї та кількість грошей.
У наступних \(n\) рядках задано по два цілих числа \(w_i\) та \(a_i\) — вартість та впевненість відповідно.
Вихідні дані
В одному рядку виведіть ціле число — максимальну впевненість, що можна отримати, вибравши певний набір зброї.
Обмеження
\(1 \le n \le 100\),
\(1 \le m \le 10^5\),
\(1 \le w_i \le 10^3\),
\(1 \le a_i \le 10^3\).
Приклади
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 3 100 99 99 50 50 50 50 | 100 |
| Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
|---|