题目描述

双11临近，小L的购物车中有 $n$ 件物品，但他的预算只有 $m$ 元。

每件物品有对应的类别 $a_i$ 和价格 $v_i$。

小L有个习惯：只要购买某类物品中的一件，就必须买下该类别所有物品。

请帮他计算在满足这个习惯的前提下，能花费的与预算 $m$ 最接近的总价格。

输入格式

第一行输入两个整数 $n, m\ (1 \leq n,m \leq 10^4)$，分别表示物品总数和预算；

接下来 $n$ 行，每行两个数 $a_i, v_i\ (1 \leq a_i \leq n,1 \leq v_i\leq 1000)$，分别表示物品的类别和价格。

输出格式

输出一个数，表示与预算最接近的花费总价格，如果存在两种最优方案优先输出小的一种。

输入输出样例 #1

输入 #1

4 6
1 2
1 3
2 4
3 5

输出 #1

5