Хамгийн ойрын баазууд I

2s

512MB

2283

0%

Additional Problems I

Бааз байрлах газрыг тор хэлбэрээр илэрхийлнэ: нүд бүрт захиалагдсан эсвэл чөлөөт нэг бааз байж болно. Хоёр нүд $(x_1, y_1)$ , $(x_2, y_2)$ -ийн хоорондын зай нь Манхэттаны зай $|x_1 - x_2| + |y_1 - y_2|$ .

Чөлөөт баазаас хамгийн ойрын захиалагдсан бааз хүртэлх хамгийн их зайг ол.

Эх сурвалж: cses.fi

Оролтын формат

Эхний мөрөнд хоёр бүхэл тоо $n$ , $m$ :
захиалагдсан ба чөлөөт баазуудын тоо.

Дараагийн $n$ мөр нь захиалагдсан баазуудын байршлыг илэрхийлнэ. Мөр бүрт хоёр бүхэл тоо $x$ , $y$ байна.

Дараагийн $m$ мөр нь чөлөөт баазуудын байршлыг илэрхийлнэ. Мөр бүрт хоёр бүхэл тоо $x$ , $y$ байна.

Нүд бүрт хамгийн ихдээ нэг бааз байна гэж үзэж болно.

Гаралтын формат

Нэг бүхэл тоо хэвлэ: хамгийн ойрын захиалагдсан бааз хүртэлх хамгийн их зай.

Хязгаарлалт

$1 \le n, m \le 10^5$
$1 \le x, y \le 10^6$

Жишээ

Оролт1

Гаралт1

0.1 / 64 KiB

Редактор уншиж байна...