Supermen

Grupa starsza

Supermen znowu ratuje świat! Aby to zrobić, musi za wszelką cenę dotrzeć do pokoju, w którym zły Wujek-Sam-Tu więzi piękną Cathreen.

Supermen potrafi: latać z prędkością v na sekundę, spadając co sekundę o jedno piętro w dół, chodzić pieszo z prędkością w na sekundę, spadać na niższe piętro budynku w jedną sekundę, wchodzić po schodach zużywając 10 sekund na wejście na piętro wyżej. Nie może wykonywać tych operacji z innymi prędkościami.

Potrafi się poruszać tylko między budynkami tylko, gdy leżą na jednej linii poziomej lub pionowej (patrząc z góry na mapę) i nie ma między nimi żadnego innego budynku.

Zarówno czas przebycia przez Supermena jakiejś drogi między miastami, jak i liczbę pięter, o jakie spadł podczas lotu pomiędzy budynkami, zaokrąglamy w górę.

Oczywiście jeśli Supermen spadnie na ziemię w czasie lotu między miastami, zaczyna iść pieszo tą samą trasą.

Jeśli Supermen dolatuje do budynku będąc na wysokości piętra, którego nie ma w tym budynku, turbulencje zmuszają go do wylądowania na najwyższym piętrze tego budynku.

Wszystkie budynki w mieście mają do 10 pięter.

Są one rozmieszczone na siatce o współrzędnych całkowitych.

Budynek, z którego Supermen wyrusza, ma numer 1, zaś budynek docelowy ma numer n. Supermen zaczyna na parterze budynku 1, a kończy na najwyższym piętrze budynku n.

Wejście

W pierwszym wierszu wejścia znajdują liczby całkowite n,v,w, 1<=n<=10000, 1<=v<=2000000000, 1<=w<=2000000000.

Potem następuje n wierszy, i-ty z nich składający się z trzech liczb całkowitych x,y,b, 0<=x<=1000000000, 0<=y<=1000000000, 1<=b<=10. x,y to współrzędne i-tego budynku na płaszczyźnie, b to liczba pięter w tym budynku (razem z parterem).

Wyjście

W pierwszym i jedynym wierszu wyjścia powinnien znajdować się minimalny czas, w jakim Supermen może dotrzeć na najwyższe piętro budynku n z najniższego piętra budynku 1. Jeśli Supermen nie może tam dotrzeć, wypisz NIE.

Przykład

Wejście:

6 40 3
0 49 5
0 0 10
21 0 7
47 49 1
47 17 3
21 17 10

Wyjście:

117

Wyjaśnienie przykładu:

Supermen jest w 1, wchodzi na pierwsze piętro w 10s, leci przez 1s w kierunku budynku 2, idzie przez 3s, jest w 2, idzie 7s do budynku 3, idzie 6s do budynku 6, gdzie wchodzi na 10 piętro w 90s. Daje to łącznie 10+1+3+7+6+90=117 sekund.