以下是翻译后的文本，使用Markdown格式进行显示：

形式语法是一种用于描述语言的方法。在这里，所谓的语言是终结符号序列的集合。形式语法由生成规则的集合构成。然后，可以将语言定义为从起始符号应用生成规则生成的可行终结符号序列的集合。一个生成规则的应用示例是，通过应用生成规则 A → ab 一次，可以将 AAB 转换为 AabB。常见的形式语法包括正则文法和上下文无关文法。这个问题涉及处理无限制的文法。

输入

输入按照以下格式给出。给出的数字均为整数。$m$ $n$ $a_1$ $b_1$ $a_2$ $b_2$ : $a_m$ $b_m$ 其中，$m$ 表示给定的生成规则的数量，$n$ 表示要生成的1的个数。 $a_i$、$b_i$ 表示生成规则中 $a_i$ 个的1变为 $b_i$ 个1。例如，$a_i = 2$，$b_i = 3$ 表示将11变为111。 通过这些信息，形式语言 $G = (V, Σ, P, S)$ 被定义出来。非终结符号 $V = \\{S\\}$，终结符号 $Σ = \\{1\\}$，起始符号为 $S$。生成规则 $P$ 包括 $S→1$ 和输入给出的生成规则。

约束

• $1 ≦ m ≦ 300^2$
• $1 ≦ n ≦ 10000$
• $1 ≦ a_i ≦ 300$
• $1 ≦ b_i ≦ 300$
• 如果 $i ≠ j$，则 $a_i ≠ a_j$ 或 $b_i ≠ b_j$

输出

求从起始符号 $S$ 开始，生成 $n$ 个1所需的最少生成规则次数。如果不可能，则输出 -1。

示例输入1

2 5
1 2
3 5

示例输出1

4

• 生成规则为 $\\{S → 1,\\ 1 → 11,\\ 111 → 11111\\}$。
• 经过 $S → 1 → 11 → 111 → 11111$ 共计4次生成规则应用。

示例输入2

2 6
1 3
5 3

示例输出2

-1

• 生成规则为 $\\{S → 1,\\ 1 → 111,\\ 11111 → 111\\}$。