Menzurki

Limit pamięci: 32 MB

Bajtazar pilnie potrzebuje odmierzyć mililitrów wody. W tym celu udał się do specjalistycznego sklepu trudniącego się sprowadzaniem odpowiedniego sprzętu. Niestety przyrządy do odmierzania wody wyszły nieco z mody i okazało się, że sklep został postawiony w stan likwidacji. Większość przyrządów została wyprzedana i jedynie pozostały dwie identyczne wadliwe menzurki. Wada polegała na tym, że zostały na nich nadrukowane tylko niektóre podziałki określające ilość wody w mililitrach. Ponieważ Bajtazar był pod ścianą, więc kupił te menzurki. Teraz stanął przed kolejnym problemem: jak najszybciej odmierzyć te mililitrów za pomocą takiego wadliwego sprzętu.

Na początku obie menzurki są puste. Możliwe operacje jakie można wykonywać to:

• dolanie wody z kranu do menzurki do wybranej podziałki,
• odlanie wody do zlewu do wybranej podziałki,
• przelanie z jednej menzurki do drugiej tak, aby ilość wody w pierwszej menzurce zmniejszyła się do wybranej podziałki,
• przelanie z jednej menzurki do drugiej tak, aby ilość wody w drugiej menzurce zwiększyła się do wybranej podziałki.

Zadanie

Twoim zadaniem jest określić ile najmniej operacji będzie potrzebnych lub stwierdzić, że niestety zadanej ilości wody nie da się odmierzyć.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą dodatnią () określającą liczbę podziałek na menzurce. W drugim wierszu znajduje się rosnący ciąg liczb całkowitych pooddzielanych pojedynczymi odstępami oznaczających wartości kolejnych podziałek. Pierwsza podziałka jest zawsze równa . Ostatnia podziałka () jest zarazem pojemnością menzurki. W trzecim i ostatnim wierszu znajduje się jedna liczba ().

Wyjście

Jeśli nie można odmierzyć zadanej ilości wody, należy wypisać jedno słowo NIE. W przeciwnym przypadku należy wypisać najmniejszą liczbę operacji, jaka jest potrzebna do odmierzenia wody.

Przykład

Dla danych wejściowych:

4
0 2 5 15
9

poprawną odpowiedzią jest:

5

Autor zadania: Jakub Pawlewicz.