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$-р төрлийн мэлхий эхлээд хоёр дахь дов руу, дараа нь дөрөв дэх, эцэст нь тав дахь дов руу үсэрч чадна.

Гурав дахь жишээнд өөр дов руу хүрч чадах мэлхий байхгүй.

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