Codeforces Round #803 (Div. 2)
2 өдрийн дараа |
Codeforces Round #804 (Div. 2)
8 өдрийн дараа |
F. Үсэрч буй мэлхийнүүд
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Тэгш өнцөгт хэлбэртэй намагт $10$ төрлийн мэлхийнүүд амьдардаг. $i$-р төрлийн мэлхий $X$ эсвэл $Y$-тэнхлэгийн дагуу нэг довноос нөгөө дов руу яг $i$ нэгжээр үсэрч чаддаг. Эхлээд бүх мэлхийнүүд $(0, 0)$ координаттай дов дээр суусан байна. Танд намагт байгаа бусад бүх довнуудын координатыг өгсөн байгаа. Мэлхийнүүд $(0, 0)$ координаттай довноос эхлэн довноос дов руу үсрэн явсаар тэдгээр мэлхийний аль нэг нь хүрч чадах хамгийн хол орших "Манхэттэний зай"-г ол.
"Манхэттэний зай" гэдэг нь $(x_{1}, y_{1})$ болон $(x_{2}, y_{2})$ цэгүүдийн хувьд $|x_{1} - x_{2}| + |y_{1} - y_{2}|$ зайг хэлнэ.
Оролт
Эхний мөрөнд довнуудын тоо болох $N$ ($1 ≤ N ≤ 100$) бүхэл тоо байна.
Дараагийн $N$ мөрүүдэд "X Y" ($-20 ≤ X, Y ≤ 20$) хэлбэрээр довнуудын координатууд өгөгдөнө. Бүх довнууд хоорондоо ялгаатай байх бөгөөд тэдгээрийн аль нь ч $(0, 0)$ координат дээр байж болохгүй.
Гаралт
Нэг бүхэл тоо хэвлэнэ. Энэ нь мэлхийнүүдийн довноос дов руу үсэрсээр хүрч чадах хамгийн их Манхэттэний зай юм.
Орчуулсан: Даариймаа
Жишээ тэстүүд
Оролт
3 0 1 0 -2 0 3
Гаралт
3
Оролт
5 0 1 0 2 0 3 2 2 2 4
Гаралт
6
Оролт
1 18 0
Гаралт
0
Тэмдэглэл
Эхний жишээнд $1$-р төрлийн мэлхий нэгдүгээр дов руу, $2$-р төрлийн мэлхий хоёрдугаар дов руу, $3$-р төрлийн мэлхий гуравдугаар дов руу үсэрч чадна.
Хоёр дахь жишээнд $2$-р төрлийн мэлхий эхлээд хоёр дахь дов руу, дараа нь дөрөв дэх, эцэст нь тав дахь дов руу үсэрч чадна.
Гурав дахь жишээнд өөр дов руу хүрч чадах мэлхий байхгүй.