该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

春天来临，岐岐带领小朋友们计划一次愉快的春游野餐，为此他们需要去超市购买各种美食。

题目描述

给定 $n$ 种食物，第 $i$ 种食物有 $a_i$ 份，美味度为 $b_i$。为了方便操作，你需要选出份数最少的食物使得总美味度不小于 $m$。如果无法满足要求，输出 $-1$。

输入格式

第一行输入两个整数 $n, m$，分别表示食物种数和最小总美味度要求。
接下来 $n$ 行，每行输入两个整数 $a_i, b_i$，分别表示第 $i$ 种食物的份数和对应的美味度。

输出格式

输出一行一个整数，表示达到要求所需的最少食物份数，如果无法满足要求则输出 $-1$。

样例

3 20
20 1
3 2
1 5

13

3 20
20 1
3 5
1 5

4

样例解释

样例 1：先选 1 份美味度为 5 的，再选 3 份美味度为 2 的，最后选 9 份美味度为 1 的，累计美味度 $5 + 3 \times 2 + 9 \times 1 = 20$，共计 $1 + 3 + 9 = 13$ 份。
样例 2：共有 4 份美味度为 5 的食物，正好满足 $4 \times 5 = 20$，所以最少需要 4 份。

数据范围

• 对于 $10\%$ 的数据，$n = 1$；
• 对于另外 $10\%$ 的数据，$m = 1$；
• 对于另外 $20\%$ 的数据，$1 \le n, a_i \le 7$；
• 对于 $100\%$ 的数据，$1 \le n \le 10^5,\;1 \le a_i, b_i, m \le 10^9$。

附件