Aby otworzyć Sezam, trzeba mieć komplet co najmniej z żetonów złotych, s — srebrnych i m —miedzianych.

Alibaba ma początkowo pewną liczbą żetonów każdego rodzaju i może je wymieniać u strażnika Sezamu według ściśle określonych reguł.

Każda reguła jest postaci:

z₁, s₁, m₁ -> z₂, s₂, m₂ (z_i, s_i, m_i należą do {0,1,2,3,4})

gdzie: z₁, s₁, m₁ oznaczają odpowiednio liczby żetonów złotych, srebrnych i miedzianych, jakie Alibaba musi dać strażnikowi, zaś z₂, s₂, m₂ - liczby żetonów złotych, srebrnych i miedzianych, które otrzyma w wyniku transakcji wymiany.

Żetony otrzymane w wyniku transakcji można wymieniać w kolejnych transakcjach.

Zadanie

• wczytuje z pliku tekstowego ALI.IN zestawy danych, z których każdy zawiera:
  • liczby żetonów złotych, srebrnych i miedzianych znajdujących się początkowo w posiadaniu Alibaby
  • opis kompletu żetonów otwierającego Sezam, oraz reguły transakcji;
• dla każdego zestawu danych stwierdza, czy istnieje skończony ciąg transakcji, który pozwoli Alibabie zgromadzić komplet żetonów otwierający Sezam i jeśli tak, znajduje i zapisuje w pliku tekstowym ALI.OUT minimalną długość takiego ciągu, a w przeciwnym przypadku zapisuje w pliku ALI.OUT odpowiedź NIE.

Wejście

Dalej są zapisane kolejno zestawy danych. Każdy zestaw danych składa się z wielu wierszy.

W pierwszym wierszu są zapisane trzy liczby całkowite nieujemne z_p, s_p, m_p należące do {0,1,2,3,4}. Są to liczby żetonów złotych, srebrnych i miedzianych, jakie na początku ma Alibaba.

W drugim wierszu są kolejne trzy liczby całkowite z, s, m należące do {0,1,2,3,4}. Są to liczby żetonów złotych, srebrnych i miedzianych, jakie trzeba mieć, aby otworzyć Sezam.

W trzecim wierszu jest zapisana liczba reguł r, gdzie 1<=r<=10.

W każdym z kolejnych r wierszy jest zapisany ciąg sześciu liczb z₁, s₁, m₁, z₂, s₂, m₂ należących do {0,1,2,3,4}. Każda taka szóstka liczb jest zapisem jednej reguły transakcji: z₁, s₁, m₁ -> z₂, s₂, m₂.

Liczby w każdym wierszu są pooddzielane pojedynczymi odstępami.

Wyjście

• jedną liczbę całkowitą nieujemną, tj. minimalną liczbę transakcji wymiany, jakich Alibaba musi dokonać, aby zgromadzić komplet żetonów otwierający Sezam,
• albo jedno słowo NIE.

Przykład
Dla pliku tekstowego ALI.IN:

2
2 2 2
3 3 3
3
0 1 1 2 0 0
1 0 1 0 2 0
1 1 0 0 0 2
1 1 1
2 2 2
4
1 0 0 0 1 0
0 1 0 0 0 1
0 0 1 1 0 0
2 0 0 0 2 2

NIE
9

Twój program powinien szukać pliku ALI.IN w katalogu bieżącym i tworzyć plik ALI.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę ALI.???, gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonalnej powinien być zapisany w pliku ALI.EXE.