Бавимося в 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