Бавимося в CS
Limits: 2 sec., 256 MiB
Сьогодні великий день. Уперше в історії збірна algotester пройшла в фінал турніру з CS: GO. І ось найважливіший раунд — кілька секунд до початку, але в цей момент команда розуміє, що в них немає стратегії для перемоги.
Вони знають, що можна купити якийсь набір зброї, кожен з яких коштує \(w_i\) грошей та дає \(a_i\) впевненості в перемозі. Кожну зброю можна купити лише 1 раз! На жаль, минулий раунд вони програли, тому кількість грошей у них обмежена й дорівнює \(m\).
Спливають останні секунди, і капітан згадав про студентів бурситету, що можуть помогти вибрати правильну стратегію. Він просить вас написати програму, що скаже, яку максимальну впевненість можна отримати при певному закупі.
Input
У першому рядку задано два цілих числа \(n\) та \(m\) — кількість наборів зброї та кількість грошей.
У наступних \(n\) рядках задано по два цілих числа \(w_i\) та \(a_i\) — вартість та впевненість відповідно.
Output
В одному рядку виведіть ціле число — максимальну впевненість, що можна отримати, вибравши певний набір зброї.
Constraints
\(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\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 3 100 99 99 50 50 50 50 | 100 |
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|