Background

传说十八世纪的某一天，欧拉在圣彼得堡研究一个极其困难的数学问题。

他从早上算到晚上，草稿纸写满了整张桌子，却始终没有找到答案。这时，他突然意识到：

“问题可能不是数学太难，而是咖啡不够。”

于是欧拉来到附近的一家咖啡馆。老板非常欣赏数学家，每一种咖啡都准备了无限多杯，还提出了一个挑战：

“如果您能恰好花完带来的金币，今天用的草稿纸，我包了。”

欧拉看了看已经写满的笔记本，立刻接受了挑战。

Description

咖啡馆共有 $n$ 种咖啡，第 $i$ 种咖啡每杯售价为 $v_i$ 个金币，喝完可以获得 $w_i$ 点灵感值。

欧拉带了 $m$ 个金币。他可以购买任意数量的咖啡，也可以多次购买同一种咖啡，但花费的金币总数必须恰好等于 $m$。

每杯咖啡的灵感值可以累加，即使重复饮用同一种咖啡，获得的灵感值也不会减少。

请计算欧拉在恰好花完所有金币的前提下，最多能获得多少点灵感值。如果无法恰好花完，输出 -1。

当然，后来欧拉究竟有没有靠这些咖啡解决那个数学问题，故事并没有交代。但据咖啡馆老板回忆：

“我不知道他最后算出了什么，我只知道他连续点了七杯一样的咖啡。”

Format

Input

第一行包含两个整数 $n$ 和 $m$，分别表示咖啡的种类数和欧拉带来的金币数。

接下来 $n$ 行，每行包含两个整数 $v_i$ 和 $w_i$，分别表示第 $i$ 种咖啡的单杯售价和单杯灵感值。

Output

输出一个整数，表示恰好花完 $m$ 个金币时能够获得的最大灵感值。如果无法恰好花完，输出 -1。

Samples

3 10
3 5
4 6
5 7

16

购买两杯售价为 $3$ 的咖啡和一杯售价为 $4$ 的咖啡，恰好花费 $10$ 个金币，获得 $5+5+6=16$ 点灵感值。

2 7
4 10
6 18

-1

所有咖啡的售价均为偶数，无法恰好花费 $7$ 个金币。

Limitation

对于所有测试数据：

• $1 \le n \le 5$；
• $1 \le m \le 15$；
• $1 \le v_i \le 20$；
• $1 \le w_i \le 100$。

不同种类的咖啡可以有相同的售价或灵感值。每个输入文件只包含一组测试数据。

时间限制：2 秒。空间限制：256 MiB。