You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

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。