問題敘述
小涵撿到了一個神奇的轉輪。這個轉輪有 n 個數字,每個數字每轉一次會依照下列的順序變化:
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 0 (接開頭)
因為那是個神奇的轉輪,你不能單獨操作一個轉輪上的數字,你必須依照一些特定的規則操作這個轉輪。
現在告訴你轉輪上原本的數,與一些操作轉輪的規則(如輸入說明所示),希望你能透過這些規則將轉輪轉為另一個數。
輸入說明
第一行輸入一個正整數 n,表示轉輪上共有幾個數字。
第二行輸入一個正整數 m,表示共有幾種操作轉輪的規則。
接下來的 m 行,每行表示一種操作轉輪的規則。每行共有 n 個整數 R1, R2, ..., Rn ,表示依照此規則操作一次轉輪,可以將轉輪上的第1個數轉 R1 次,將轉輪上的第2個數轉 R2 次,……,將轉輪上的第n個數轉 Rn 次。
最後一行有兩個整數 st, ed,表示轉輪上原本的數是 st ,你希望透過若干次操作使得轉輪上的數成為 ed。
( 1<= n <= 7; 1<= m <= 50, 0 <= Ri <= 2^31-1)
輸出說明
請輸出最少需要幾次操作,可以使轉輪上的數成為ed 。
測試資料中不會有無法使轉輪上的數成為 ed 的情形。
範例輸入
3
2
1 0 0
0 2 1
568 121
範例輸出
9