Niedaleko 2

Limit pamięci: 64 MB

Jak mówi znane przysłowie, niedaleko pada jabłko od jabłoni. Twoim zadaniem będzie eksperymentalne sprawdzenie tego przysłowia. Położenia jabłoni i jabłek możemy utożsamiać z punktami na płaszczyźnie. Odległość między punktami liczymy za pomocą metryki miejskiej, tzn.:

Zakładamy, że każde jabłko spadło z najbliższej mu jabłoni.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis położeń jabłek i jabłoni,
• wyznaczy minimum z odległości jabłek od ich jabłoni,
• wypisze wynik na standardowe wyjście.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite oraz (), oddzielone pojedynczym odstępem i oznaczające liczbę jabłoni oraz liczbę jabłek. Drugi wiersz wejścia zawiera liczb całkowitych z przedziału , pooddzielanych pojedynczymi odstępami i oznaczających pary współrzędnych jabłoni: . Trzeci wiersz wejścia zawiera liczb całkowitych z przedziału , pooddzielanych pojedynczymi odstępami i oznaczających pary współrzędnych jabłek: . Zarówno jabłonie, jak i jabłka traktujemy tutaj jako punkty na płaszczyźnie; w jednym punkcie może się znajdować dowolnie wiele jabłoni i dowolnie wiele jabłek.

Wyjście

Pierwszy i jedyny wiersz wyjścia powinien zawierać minimum z odległości jabłek od ich jabłoni.

Przykład

Dla danych wejściowych:

3 4
0 2 2 0 2 2
1 1 2 1 2 3 1 4

poprawną odpowiedzią jest:

1

Autor zadania: Jakub Radoszewski.