A - 1→1 Editorial /

Time Limit: 2 sec / Memory Limit: 64 MB

言語を記述するものとして形式文法があります。
ここでいう言語とは終端記号の列の集合です。
形式文法を構成するものとして生成規則の集合が定義されます。
そして、開始記号から生成規則を適用して作ることのできる終端記号の列の集合、として言語を定義することができます。
生成規則の適用の例としては、生成規則 A → ab を1回適用することで 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 を出力せよ。

Input 1

2 5
1 2
3 5

Output 1

4
  • 生成規則は、\{S → 1,\ 1 → 11,\ 111 → 11111\} である。
  • S → 1 → 11 → 111 → 11111 で 4 回となる。

Input 2

2 6
1 3
5 3

Output 2

-1
  • 生成規則は、\{S → 1,\ 1 → 111,\ 11111 → 111\} である。