E. Савангийн Дуурь

хугацааны хязгаарлалт 6 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

$k$ ширхэг ялгаатай цэгүүд дээр метроны буудал бүхий координатын хавтгайг төсөөлнө үү. Нэг буудлаас нөгөө буудалруу агшин зуурт очдог(замд зарцуулах хугацаа 0) ба та зөвхөн нэг буудлаас өөр нэг буудалруу шилжихдээ зорьсон буудалдаа хүрэхээсээ өмнө буюу буудалгүй хоосон газар бууж болохгүй.

Координатууд нь өгөгдсөн нийт $n$ ширхэг одойчууд уг хавтгай дээр байгаа ба тэд бүгд нэг цэг дээр цуглан савангийн дуурь үзэцгээхийг хүсэж байгаа. Үүний тулд тэд цуглах цэгээ сонгоод хөдлөж эхлэсэн ба $(x, y)$ цэг дээр буй одой нэг секундэд $(x-1, y), (x+1, y), (x, y-1), (x, y+1)$ цэгүүдийн аль нэгрүү хөдлөж чадна. Мөн одойчууд метроны буудлуудыг хэдэн ч удаа ашиглаж болох ба нэг метроны буудлаас өөр нэг метроны буудал ороход шаардагдах хугацаа 0. Одойчууд хөдлөж байхдаа бие биендээ ямар нэгэн байдлаар садаа болдоггүй.(өөр хэлвэл тэд нэгэн зэрэг бие биенээсээ хамааралгүй хөдөлцгөөдөг)

Бүх одойчууд нэг цэгт цуглахад шаардлагатай хамгийн бага хугацааг олно уу.

Оролт

Эхний мөрөнд хоёр бүхэл тоо $n$ ба $k(1<=n<=10^5, 0<=k<=10^5)$ буюу одойчуудын тоо ба метроны буудлуудын тоонууд байрлана.

Дараагийн $n$ мөрөнд одойчуудын координатууд өгөгдөх ба $i$-р мөрөнд хоорондоо хоосон зайгаар тусгаарлагдсан 2 бүхэл тоо $x_i, y_i(|x_i|, |y_i|<=10^8)$ байх бөгөөд бүх одойчуудын координатууд ялгаатай.

Дараагийн $k$ мөрөнд метроны буудлуудын координатууд өгөгдөх ба $t$-р мөрөнд хоорондоо хоосон зайгаар тусгаарлагдсан 2 бүхэл тоо $x_t, y_t(|x_t|, |y_t|<=10^8)$ байх бөгөөд бүх буудлуудын координатууд ялгаатай.

Гаралт

Ганцхан бүхэл тоо хэвлэ - бүх одойчууд нэг цэгт цуглахад шаардлагатай хамгийн бага хугацаа.

Орчуулсан: devman

Жишээ тэстүүд

Оролт
1 0
2 -2
Гаралт
0
Оролт
2 2
5 -3
-4 -5
-4 0
-3 -2
Гаралт
6
Сэтгэгдлүүдийг ачааллаж байна...