题目描述

$m$表示变化规则的数量，$n$表示要生成$1$的数量。

对于生成规则$a_{i},b_{i}$而言，它表示可以将原字符串中的$a_{i}$个$1$变为$b_{i}$个$1$。例如，$a_{i}=2,b_{i}=3$，表示原字符串中$11$可以变为$111$

现在，原字符串中只有$1$个$1$，要求你使用最少的变化次数将字符串变成$n$个$1$。

输入输出格式

输入格式

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

第$2$~$m+1$行，每行两个整数$a_{i},b_{i}$；

输出格式

如果能将字符串变成$n$个$1$，输出$($变化次数$+1)$，否则输出$-1$。

说明

数据范围

• $1≤m≤300^{2}$
• $1≤n≤10000$
• $1≤a_{i},b_{i}≤300$
• 当$i≠j$时保证$a_{i}≠a_{j}$且$b_{i}≠b_{j}$

样例说明

样例$1$

规则为：

$1->11$

$111->11111$

那么一个$1$变成$11111$需要经过下面这些步骤：

1->11

11->111

111->1111

变化次数为$3$，故答案为$4$。

样例$2$

规则为：

$1->111$

$11111->111$

那么一个$1$不可能变成$111111$，故答案为$-1$。