Bessie שומעת שמטר מטאורים יוצא דופן מתקרב: הם יפגעו בארץ וישמידו כל דבר שיפגעו בו. מודאגת, היא מחליטה למצוא דרך למקום בטוח, שלעולם לא יושמד בידי מטאור. כעת היא רועה בראשית המישור ורוצה לעבור למקום חדש ובטוח יותר בלי להיהרס בדרך.
יפגעו $M$ מטאורים, $(1 \le M \le 50,000)$. מטאור $i$ פוגע ב־$(X_{i}, Y_{i})$, $(0 \le X_{i} \le 300; 0 \le Y_{i} \le 300)$, בזמן $T_{i}$, $(0 \le T_{i} \le 1,000)$. הוא משמיד אותה ואת ארבע נקודות הסריג השכנות אופקית או אנכית.
Bessie עוזבת את הראשית בזמן $0$ ויכולה לנוע ברביע הראשון במקביל לצירים ביחידת מרחק לשנייה אל כל שכן שטרם נהרס (לרוב ארבעה). אסור לה להיות בנקודה בזמן השמדתה או אחריו.
מצאו את הזמן המזערי להגיע למקום בטוח.
קלט
קראו מהקלט התקני.
שורה $1$: שלם אחד $M$.
שורות $2,\ldots,M+1$: שורה $i+1$ מכילה שלושה שלמים מופרדי רווחים: $X_{i}$, $Y_{i}$, $T_{i}$.
פלט
כתבו לפלט התקני.
- שורה $1$: הזמן המזערי או $-1$ אם אי אפשר.
דוגמאות
קלט 1
4 0 0 2 2 1 2 1 1 2 0 3 5
פלט 1
5
הערה
ארבעה מטאורים פוגעים ב־$(0, 0)$, $(2, 1)$, $(1, 1)$, $(0, 3)$ בזמנים $2$, $2$, $2$, $5$ בהתאמה.
t = 0 t = 2 t = 5 5|. . . . . . . 5|. . . . . . . 5|. . . . . . . 4|. . . . . . . 4|. . . . . . . 4|# . . . . . . * = פגיעת מטאור 3|. . . . . . . 3|. . . . . . . 3|* # . . . . . 2|. . . . . . . 2|. # # . . . . 2|# # # . . . . # = מרעה מושמד 1|. . . . . . . 1|# * * # . . . 1|# # # # . . . 0|B . . . . . . 0|* # # . . . . 0|# # # . . . . -------------- -------------- -------------- 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1 2 3 4 5 6
בציור בזמן $t=5$ הנקודה הבטוחה הקרובה ביותר היא $(3, 0)$ אך המטאור השני חוסם מוקדם מדי את הדרך. הבאה, $(4,0)$, נחסמת גם היא מוקדם מדי. אחריה נקודות הסריג באלכסון $(0,5)$-$(5,0)$. מהן $(0,5)$, $(1,4)$, $(2,3)$ נגישות ב־$5$ יחידות זמן.
5|. . . . . . .
4|. . . . . . .
3|3 4 5 . . . . מיקומי Bessie לאורך הזמן
2|2 . . . . . . עבור פתרון אחד
1|1 . . . . . .
0|0 . . . . . .
--------------
0 1 2 3 4 5 6מחבר הבעיה: Jeffrey Wang, 2007