题目描述

你正在经营一家特色饼干工坊，专注制作印有数字“1”的主题饼干。初始时，你手中仅有 1块数字1饼干，现在需要通过工坊的专属烘焙规则，制作出恰好 $n$ 块数字1饼干，要求使用最少的烘焙操作次数完成目标。

$m$ 表示工坊拥有的不同烘焙规则数量，$n$ 表示最终需要交付的数字1饼干总数。

每一条烘焙规则用 $(a_i, b_i)$ 表示：你可以从当前持有的饼干中，取出 $a_i$ 块数字1饼干，放入特制烘焙机中重新加工，最终得到 $b_i$ 块数字1饼干（相当于用 $a_i$ 个“1”替换为 $b_i$ 个“1”）。例如，规则 $(2, 3)$ 表示：将2块数字1饼干送入烘焙机，加工后会得到3块数字1饼干。

请你规划最优烘焙方案，用最少的操作次数将初始1块饼干变成 $n$ 块饼干。

输入格式

第一行，两个整数 $m, n$；

第2~$m+1$ 行，每行两个整数 $a_i, b_i$，表示一条烘焙规则。

输出格式

如果能成功制作出 $n$ 块数字1饼干，输出 $($烘焙操作次数 $+ 1)$，否则输出 $-1$。

输入输出样例

2 5
1 2
3 5

4

2 6
1 3
5 3

-1

说明/提示

• $1 \leq m \leq 300^2$
• $1 \leq n \leq 10000$
• $1 \leq a_i, b_i \leq 300$
• 当 $i \neq j$ 时，保证 $a_i \neq a_j$ 且 $b_i \neq b_j$

样例1

烘焙规则： 1 → 11（1块数字1饼干烘焙成2块） 111 → 11111（3块数字1饼干烘焙成5块）

制作流程： 1块 → 2块（第1次烘焙） 2块 → 3块（第2次烘焙，通过规则组合实现） 3块 → 5块（第3次烘焙）

烘焙操作次数为3，故答案为 $3 + 1 = 4$。

样例2

烘焙规则： 1 → 111（1块数字1饼干烘焙成3块） 11111 → 111（5块数字1饼干烘焙成3块）

结论：从1块数字1饼干出发，无法通过现有规则制作出6块数字1饼干，故答案为 $-1$。