Problem description

Podczas budowy tajnej pingwiniej bazy doszło do pewnego incydentu …

Z żołądka Rico, w nieznanych nikomu okolicznościach, na świat wydostała się bomba; na domiar złego bomba była odpalona. Jak można się domyślić, wskutek tego wydarzenia doszło do eksplozji. Kaboom. Wybuch doprowadził do rozszczelnienia się basenu otaczającego wybieg pingwinów, przez co codziennie ulatuje z niego K litrów wody.

Oczywiście, jeśli ze zbiornika ucieknie zbyt dużo wody, to władze Zoo zainteresują się tym incydentem, a tym bardziej zainteresują się faktem powstania tajnej bazy pod wybiegiem pingwinów, do czego, jak wiadomo, dopuścić nie można (na podstawie odcinka “Ostrożnie z życzeniami”). Dlatego też nieloty podjęły działania zapobiegawcze i za N + 1 dni zaplanowały wyprawę po materiały, które pozwolą na załatanie wycieku.

Niestety przez najbliższe N dni do basenu codziennie należy dolewać trochę wody, tak by jej poziom nie spadł poniżej A litrów, oraz nie przekroczył B litrów. Dokładnie każdego z N dni najpierw pingwiny dolewają X_i litrów wody, następnie z basenu wycieka K litrów wody, a następnie Alice robi obchód i sprawdza poziom wody na wybiegu pingwinów; jeśli wody będzie zbyt mało lub zbyt dużo, to oznacza to tarapaty dla pingwinów.

Pingwiny zastanawiają się teraz, ile wody należy nalać do basenu na początku, aby do tarapatów nie doszło. Twoim zadaniem będzie im pomóc i napisać program, który stwierdzi czy istnieje takie początkowe napełnienie basenu, że jeśli pingwiny będą codziennie dolewały wodę zgodnie z planem, to każdego dnia będzie ona w odpowiednim przedziale.

Uwaga: z basenu nie może wyciec więcej wody, niż w nim jest, przykładowo, jeśli w basenie znajduje się 5 litrów wody, a wyciec z niego ma 6 litrów, to po wycieku w basenie znajdować się będzie 0 litrów wody.

Wejście

W pierwszym wierszu wejścia znajdują się cztery liczby naturalne N, K, A i B, pooddzielane pojedynczymi odstępami i oznaczające odpowiednio liczbę dni, przez które do basenu będzie dolewana woda, liczbę litrów wody, która będzie codziennie wyciekać z basenu, minimalną liczbę litrów oraz maksymalną liczbę litrów wody dopuszczalną przez Alice w basenie. W drugim i ostatnim wierszu wejścia znajduje się ciąg N liczb naturalnych X_i, pooddzielanych pojedynczymi odstępami i oznaczających liczbę litrów wody, która dolewana będzie w kolejnych dniach do basenu.

Wyjście

W pierwszym wierszu wyjścia powinna znaleźć się jedna liczba naturalna – maksymalny początkowy stan napełnienia basenu, dla którego stan wody nie spadnie poniżej A litrów, oraz nie przekroczy B litrów wody. Jeśli poszukiwany stan napełnienia wody nie istnieje, zamiast tego należy wypisać słowo NIE.

Ograniczenia

1 ≤ N ≤ 100 000, 0 ≤ K, X_i ≤ 10⁹, 0 ≤ A ≤ B ≤ 10⁹.

Przykład

7 2 2 5
3 3 1 3 4 0 1

1

4 3 7 9
3 5 4 0

NIE

7 4 0 4
2 3 3 5 2 8 1

5

Niezbędny przypis: postacie z treści pochodzą z serialu “Pingwiny z Madagaskaru”.