Problem description

Przejechawszy całą Drogę Panamerykańską, Karol zawrócił i pojechał do Nowego Jorku, gdzie, zaintrygowany niezwykłą regularnością układu tamtejszych ulic, postanowił zostać taksówkarzem.

Na telefonie Karola działa aplikacja Taxi Driver, która pokazuje mu dostępne zlecenia opisane punktem początkowym, końcowym i zapłatą w dolarach za wykonanie kursu. Nowy Jork jest na tyle dużym miastem, że nawet jeśli Karol wykona jakieś zlecenie, to po chwili i tak znajdzie się kolejna osoba, która potrzebuje przejechać tę samą trasę za tę samą opłatę – innymi słowy zlecenia nie wygasają.

Dla uproszczenia przyjmujemy, że interesujący Karola fragment Nowego Jorku to sieć ulic, z których każde dwie są równoległe lub prostopadłe i każde dwie sąsiednie równoległe ulice są od siebie oddalone o 1 km, a ponadto początek i koniec każdego zlecenia to skrzyżowanie dwóch ulic. Przyjmiemy więc układ współrzędnych, w którym (x,y) to skrzyżowanie x-tej ulicy w kierunku północ-południe z y-tą ulicą w kierunku wschód-zachód. W szczególności odległość między punktem (x,y) i punktem (x′,y′) to |x−x′| + |y−y′| kilometrów.

Przejechanie jednego kilometra zawsze kosztuje Karola 1 dolara, a jego dzień pracy zaczyna się w punkcie (1,1) i kończy w punkcie (X_K,Y_K), co oznacza, że Karol może być danego dnia stratny, bo i tak musi przejechać z (1,1) do (X_K,Y_K).

Jaki największy zysk może osiągnąć Karol? Czy Karol może wybierać zlecenia tak, by zarobić dowolnie dużo?

Napisz program, który wczyta opis zleceń dostępnych w aplikacji Taxi Driver, wyznaczy optymalny scenariusz jazdy dla Karola i wypisze maksymalny zysk na standardowe wyjście lub poinformuje, że Karol może zarobić dowolnie dużo.

Wejście

W pierwszym wierszu wejścia znajdują się trzy dodatnie liczby całkowite N, X_K, Y_K, pooddzielane pojedynczymi odstępami i oznaczające kolejno: liczbę zleceń dostępnych w aplikacji Taxi Driver i położenie punktu końcowego.

W każdym z kolejnych N wierszy wejścia znajduje się pięć dodatnich liczb całkowitych X_S, i, Y_S, i, X_E, i, Y_E, i, Z_i, pooddzielanych pojedynczymi odstępami i oznaczających, że istnieje zlecenie przewozu z punktu (X_S, i,Y_S, i) do punktu (X_E, i,Y_E, i), za które Karol otrzyma Z_i dolarów.

Wyjście

Jeśli Karol może uzyskać dowolnie duży zysk, to w jedynym wierszu wyjścia powinno znaleźć się słowo KREZUS.

W przeciwnym razie, w jedynym wierszu wyjścia powinna znaleźć się jedna liczba całkowita określająca maksymalny zysk Karola w dolarach.

Ograniczenia

1 ≤ N ≤ 2 000, 1 ≤ X_⋅,i, Y_⋅,i, X_K, Y_K ≤ 1 000 000, 1 ≤ Z_i ≤ 10 000 000.

Przykład

1 10 10
4 3 7 8 10

-8

1 5 3
10 10 20 20 25

-6

2 3 4
2 2 8 3 12
6 2 4 5 9

KREZUS

3 8 6
5 5 4 10 9
5 8 8 5 9
2 2 5 4 8

2