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。

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

第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->11111

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