Qaydalar#8775
Cənab Sem və cənab Yuri, hər ikisi 80 yaşdan yuxarı olan şəxslər, hamının əməl etməli olduğuna inandıqları qaydalar təyin etməyə qəribə dərəcədə güclü meylləri var. Cəmiyyətə təsirlərindən istifadə edərək, bu qaydaları hər kəsə tətbiq etməyə çalışırlar.
Bağçada ağacın bir xətt boyunca düzülməsi vəziyyətinə baxaq. Hər bir ağacı (, 0) nöqtəsində əsası, (, ) nöqtəsində zirvəsi olan şaquli bir parça kimi təsəvvür edə bilərik; burada ağacın xətt boyunca yerləşdiyi mövqeyi, isə onun hündürlüyüdür.
Onların son qaydalarından birinə əsasən, hər bir ağacın zirvəsi bir fənər tərəfindən işıqlandırılmalıdır. Bunu təmin etmək üçün bəzi ağacların budanması (hündürlüyünün azaldılması) lazım ola bilər. Konkret olaraq, fənərin koordinatları (, )-dir və qaydaya görə, fənərdən hər bir ağacın zirvəsinə çəkilən xətt parçası heç bir digər ağacı kəsməməlidir. Ağac bu parçaya sadəcə toxunarsa, budama tələb olunmur. Hətta ağacın hündürlüyü sıfra endirilsə belə, yenə də ağac hesab olunur.
Bu tapşırığın iştirakçısı olaraq, təqdim olunan qaydaya əməl etmək üçün ağacların ümumilikdə nə qədər budanmalı olduğunu (hündürlüyün nə qədər azaldılmalı olduğunu) müəyyənləşdirməlisiniz.
Birinci sətirdə parkdakı ağacların sayı olan bir tam ədəd (1 \le n \le 10^5) verilir. Sonrakı sətirdən hər birində iki tam ədəd və (0 \le x[i] \le 10^9, 1 \le h[i] \le 1000) — hər bir ağacın mövqeyi və hündürlüyü təsvir olunur. Növbəti sətirdə iki tam ədəd və (0 \le x \le 10^9, 1 \le y \le 1000) — fənərin koordinatları verilib. Zəmanət verilir ki, ağacların mövqeləri artan sırada verilib və heç bir ağac fənər ilə eyni mövqedə yerləşmir.
Bir ədəd çıxış verin — qaydaya riayət etmək üçün ağacların nə qədər budanmalı olduğunu göstərən minimum ümumi uzunluq. Cavabınızın mütləq və ya nisbi xətası 10^{-6}-dan artıq olmamalıdır. Rəsmi olaraq, qoy cavabınız , düzgün cavab isə olsun. Həlliniz |a-b| / \max(1,|b|) \leq 10^{-6} şərtini ödədikdə qəbul olunacaq.
Nümunə 1