ברגע מסוים, הנקרא הרגע ההתחלתי, רוכבי האופניים המשתתפים במרוץ כביש נמצאים במרחקים $x_1,x_2,\ldots,x_n$ מטרים מנקודת הזינוק ($n$ הוא מספר הרוכבים הכולל). כל רוכב נע במהירות קבועה משלו; המהירויות הן $v_1,v_2,\ldots,v_n$ מטרים לשנייה. כל הרוכבים נעים באותו כיוון.

כתב המסקר את התחרות רוצה לקבוע את הרגע שבו המרחק בין הרוכב המוביל לרוכב האחרון יהיה מזערי, כדי לצלם ממסוק את כל משתתפי המרוץ בבת אחת.

כתבו תוכנית שבהינתן מספר הרוכבים $n$, מיקומיהם ההתחלתיים $x_1,x_2,\ldots,x_n$ ומהירויותיהם $v_1,v_2,\ldots,v_n$, תחשב רגע $t$ שבו המרחק $l$ בין הרוכב המוביל לרוכב האחרון מזערי.

קלט

השורה הראשונה בקובץ הקלט מכילה מספר שלם $n$, מספר רוכבי האופניים.

כל אחת מ־$n$ השורות הבאות מכילה שני מספרים שלמים: $x_i$, המרחק מנקודת הזינוק לרוכב $i$ ברגע ההתחלתי ($0\le x_i\le10^7$), ו־$v_i$, מהירותו ($0\le v_i\le10^7$).

פלט

יש להדפיס לקובץ הפלט שני מספרים ממשיים: $t$, הזמן בשניות שחלף מהרגע ההתחלתי עד שהמרחק במטרים בין המוביל לאחרון יהיה מזערי, ו־$l$, מרחק זה.

המספרים $t$ ו־$l$ חייבים להיות בעלי שגיאה מוחלטת או יחסית שאינה עולה על $10^{-6}$. כלומר, אם המספר שהודפס הוא $x$ והתשובה הנכונה היא $y$, התשובה תיחשב נכונה אם $|x-y|/\max\{1,|y|\}$ אינו עולה על $10^{-6}$.

דוגמאות

קלט 1

3
0 40
30 10
40 30

פלט 1

1 30

קלט 2

5
90 100
100 70
100 70
110 60
120 35

פלט 2

0.5 5.000000000000

תתי־משימות

בבעיה זו ארבע תתי־משימות. כל תת־משימה מוערכת באמצעות קבוצת בדיקות משלה. הניקוד עבור תת־משימה ניתן רק אם עוברים את כל הבדיקות בקבוצה זו.

תת־משימה 1 (20 נקודות)

$2\le n\le50$, $0\le x_i\le1000$, $0\le v_i\le1000$. מובטח שקיימת תשובה שבה $t$ הוא מספר שלם שאינו עולה על $1000$.

תת־משימה 2 (20 נקודות)

$2\le n\le200$.

תת־משימה 3 (30 נקודות)

$2\le n\le2000$.

תת־משימה 4 (30 נקודות)

$2\le n\le10^5$.

משוב

במהלך הסבב ניתן לבקש את תוצאות הרצת התוכנית על בדיקות השופטים לכל היותר 10 פעמים. אין להגיש בקשות בתדירות גבוהה מפעם אחת בכל 5 דקות. לכל בדיקה מדווחת תוצאת הרצת התוכנית על אותה בדיקה.

בבעיה זו ניתן לבחור איזה פתרון יוערך. במקרה זה יינתן הניקוד עבור הטוב מבין הפתרונות הבאים:

• הפתרון שנבחר במפורש;
• הפתרון האחרון שהתקבל לבדיקה.

אם לא נבחר פתרון, יוערך הטוב מבין הפתרונות הבאים:

• הפתרונות שהניקוד שלהם נצפה;
• הפתרון האחרון שהתקבל לבדיקה.