+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پروفسور باقر که یک کاربر ناشی است، به بازی پو روی آورده. او امروز بخش جدیدی از این بازی را پیدا کرده و می‌خواهد آن را به روش خود انجام دهد. این بازی روی صفحه‌ی تبلتش انجام می‌شود. فرض کنید که صفحه‌ی تبلت او مانند یک صفحه مختصات دکارتی است که اضلاع پایین و چپ صفحه‌ی تبلت، محور‌های مختصات $x$ و $y$ هستند. $n$ نقطه روی این صفحه وجود دارند. این نقاط را با اعداد ۱ تا $n$ شماره گذاری میکنیم. نقطه‌ی $i$ام روی مختصات $(x_i, y_i)$ قرار گرفته‌ است. پروفسور باید روی تبلتش، دست خود را روی نقطه‌ی ۱ گذاشته و دست خود را موازی محور های مختصات (بصورت عمودی و افقی) روی صفحه‌ی تبلت حرکت دهد تا دستش به نقطه‌ی $n$ برسد و در طی این حرکت، روی صفحه‌ی تبلت در مسیر دست او خطی شکلاتی کشیده میشود. از قابلیت‌های این بازی، توانایی حرکت بین نقاط است. یعنی پروفسور می‌تواند برای کشیدن مسیری از نقطه‌ی $s$ به نقطه‌ی $t$، ابتدا مسیری بین نقطه‌ی $s$ و نقطه‌ی $i$ روی تبلت بکشد، سپس دست خود را برداشته و پس از استراحت، دوباره دستش را روی تبلت گذاشته و مسیری بین نقطه‌ی $i$ و نقطه‌ی $t$ را روی تبلت بکشد. پروفسور، امروز خیلی ناشیانه بازی کرده است؛ بطوری که دستش درد گرفته و حرکت عمودی دستش روی تبلت (در راستای محور $y$) برایش خیلی سخت است. اما پروفسور هنوز هم می‌خواهد به بازی ادامه دهد، و تلاش میکند طوری بازی کند که دستش کمترین مقدار حرکت عمودی را انجام دهد. برای رسیدن به این هدف او میتواند وقتی دستش روی صفحه‌ی تبلت نیست، تبلت را ۹۰ درجه بچرخاند! برای مثال اگر پروفسور بخواهد از نقطه‌ی ۱ با مختصات $(9, 0) $ به نقطه‌ی $n$ با مختصات $(5, 8)$ مسیری بکشد، بدون چرخاندن تبلت باید دستش ۸ واحد در راستای عمودی حرکت کند ولی اگر تبلت را ۹۰ درجه بچرخاند، می‌تواند با تنها ۴ واحد حرکت در راستای عمودی به هدفش برسد. اگر نقطه‌ی ۲ با مختصات $(5, 0)$ نیز روی صفحه وجود داشته باشد، پروفسور میتواند ابتدا بدون حرکت دادن دستش در راستای عمودی خطی از نقطه‌ی ۱ به نقطه‌ی ۲ بکشد و سپس دست خود را برداشته و تبلت را بچرخاند. حال میتواند باز هم بدون حرکت دست در راستای عمودی، خطی از نقطه‌ی ۲ به نقطه‌ی $n$ بکشد و در مجموع بدون حرکت دادن دستش بصورت عمودی، به هدفش برسد. با ورودی گرفتن مختصات نقاط، به پروفسور بگویید که حداقل مقدار حرکت عمودی دستش برای اینکه مسیری از نقطه‌ی ۱ به نقطه‌ی $n$ روی تبلتش بکشد چقدر است. # ورودی سطر اول ورودی شامل عدد $n$ است که نشان دهنده‌ ی تعداد نقاط روی صفحه است. در سطر $i$ام از هریک از $n$ سطر بعدی مختصات نقطه‌ی $i$ بصورت $x_i\ y_i$ آمده است. $$ 2 \le n \le 200\ 000$$ $$ 0 \le x_i, y_i \le 1000\ 000\ 000$$ # خروجی تنها سطر خروجی باید شامل یک عدد باشد که برابر است با کمترین مقدار حرکت عمودی دست که برای کشیدن مسیری بین نقطه‌ی ۱ و نقطه‌ی $n$ لازم است. # مثال ## ورودی نمونه ۱ ``` 2 9 0 5 8 ``` ## خروجی نمونه ۱ ``` 4 ``` ## ورودی نمونه ۲ ``` 3 9 0 5 0 5 8 ``` ## خروجی نمونه ۲ ``` 0 ``` ## ورودی نمونه ۳ ``` 5 2 2 1 1 4 5 7 1 6 7 ``` ## خروجی نمونه ۳ ``` 2 ```

حل سؤال در بانک سؤالات