A. Лонхнуудыг дахин ашиглах

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

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

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

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

Кэколэндэд дахин ашиглалтын өдөр болж байна. Энэ өдрийг тэмдэглэхийн тулд Адил ба Бера хоёр газраас лонх цуглуулж дахин ашиглах хогийн саванд хийх боломжтой газар буюу Central Perk-д очсон.

Бид Central Perk-г координатын хавтгай гэж төсөөлж болно. Энд газраар тарсан $n$ лонх байгаа ба $i$-р лонх $(x_{i}, y_{i})$ байрлалд байрласан. Адил ба Бера хоёр хоёулаа нэг удаад нэг л лонх авч явж чадна.

Адил болон Берагийн хувьд үйл явц дараах байдалтай явагдана:

  1. Лонх түүхээ зогсоох эсвэл үргэлжлүүлэн лонх цуглуулахын аль нэгийг сонгох.
  2. Хэрвээ үргэлжүүлэхээр сонгосон бол нэг лонх сонгож түүнрүүгээ алхах.
  3. Уг лонхоо аваад дахин ашиглах хогийн савруу явах.
  4. $1$-р алхамруу очих.

Адил Бера хоёр бие даан явж болно. Тэд лонхнуудыг нэгэн зэрэг авахыг зөвшөөрнө, бүх лонхыг энэ хоёрын хэн нь ч түүж болно, нэг нь түүж байхад нөгөөх нь түүхгүй амарч байж болно.

Тэд энэ үйл ажиллагаагаа тэдний алхах нийт зай (Адил-н алхсан зай болон Берагийн алхсан зайн нийлбэр) боломжит хамгийн бага байхаар зохион байгуулахыг хүсч байна. Мэдээж төгсгөлд нь бүх лонхнууд дахин ашиглах хогийн саванд байх ёстой.

Оролт

Оролтын эхний мөрөнд зургаан бүхэл тоон утга $a_{x}$, $a_{y}$, $b_{x}$, $b_{y}$, $t_{x}$ ба $t_{y}$ ($0 ≤ a_{x}, a_{y}, b_{x}, b_{y}, t_{x}, t_{y} ≤ 10^{9}$) байх ба харгалзан Адил, Бера болон хогийн савны анхны байрлалууд байна.

Хоёр дахь мөрөнд бүхэл тоон утга $n$ ($1 ≤ n ≤ 100 000$) байх ба лонхнуудын тоо юм.

Дараагийн $n$ мөр бүрт хоёр бүхэл тоон утга $x_{i}$ ба $y_{i}$ ($0 ≤ x_{i}, y_{i} ≤ 10^{9}$) байх ба $i$-р лонхны байрлал юм.

Адил, Бера, хогийн сав болон бүх лонхнуудын байрлал ялгаатай байна.

Гаралт

Бүх лонхыг дахин ашиглах хогийн саванд хийхэд Адил болон Берагийн туулах шаардлагатай нийт зайн боломжит хамгийн бага утгыг илэрхийлэх нэг бодит тоог хэвлэ. Хэрвээ таны хариултын үнэмлэхүй болон харьцангуй алдаа нь $10^{ - 6}$-с хэтрэхгүй бол зөв гэж тооцно.

Өөрөөр: таны хариултыг $a$ гэе, шүүгчийн хариултыг $b$ гэе. Шалгагч програм таны хариултыг байвал зөв гэж тооцно.

Орчуулсан: Г.Мэндбаяр

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

Оролт
3 1 1 2 0 0
3
1 1
2 1
2 3
Гаралт
11.084259940083
Оролт
5 0 4 2 2 0
5
5 2
3 0
5 5
3 5
3 3
Гаралт
33.121375178000

Тэмдэглэл

Эхний жишээг авч үзье.

Адил дараах замыг ашиглана: .

Бера дараах замыг ашиглана: .

Адил-н зам нь нэгж урттай байх бол Берагийн зам нь нэгж урттай байна.

Сэтгэгдлүүдийг ачааллаж байна...