Mokra robota

Limit pamięci: 32 MB

Dysponujemy naczyniami, gdzie . Wszystkie naczynia są początkowo całkowicie wypełnione wodą. Pojemność -tego naczynia , mierzona w litrach, jest liczbą naturalną spełniającą nierówności .

Wolno wykonywać trzy rodzaje ruchów:

• Przelanie całej zawartości z jednego naczynia do drugiego. Ruch ten można wykonać tylko wtedy, gdy w drugim naczyniu jest wystarczająco dużo wolnego miejsca.
• Dolanie wody do pełna z jednego naczynia do drugiego.
• Wylanie całej zawartości jednego naczynia do zlewu.

Zadanie

Napisz program, który:

• wczytuje ze standardowego wejścia liczbę naczyń , pojemność każdego naczynia i zadaną końcową ilość wody w każdym z naczyń,
• bada, czy można w skończonej liczbie ruchów doprowadzić do zadanej sytuacji końcowej i jeśli tak, znajduje minimalną liczbę ruchów prowadzących do niej,
• zapisuje wynik, tj. słowo NIE lub minimalną liczbę ruchów na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia jest zapisana jedna liczba całkowita dodatnia () — jest to liczba naczyń. W drugim wierszu jest zapisanych liczb naturalnych. Koleina -ta liczba jest pojemnością -tego naczynia. W trzecim wierszu jest zapisanych liczb naturalnych. Koleina -ta liczba jest zadaną końcową ilością wody w odpowiednim -tym naczyniu. Liczby w wierszach drugim i trzecim są pooddzielane pojedynczym odstępem.

Wyjście

Jeśli nie można doprowadzić do zadanej sytuacji końcowej, to w pierwszym i jedynym wierszu standardowego wyjścia należy zapisać jedno słowo NIE, a w przeciwnym przypadku minimalną liczbę ruchów prowadzących do zadanej sytuacji końcowej.

Przykład

Dla danych wejściowych:

3
3 5 5
0 0 4

poprawną odpowiedzią jest:

6

natomiast dla danych:

2
20 25
10 16

poprawnym wynikiem jest:

NIE

Autor zadania: Piotr Chrząstowski-Wachtel.