נתונות לכם $n$ שלשות של מספרים שלמים $(a_i, b_i, c_i)$, כך שמתקיים $a_i < b_i < c_i$. עליכם לבחור זוג ערכים מכל שלשה וכך ליצור $n$ קטעים. עליכם לבחור את הזוגות כך שלכל שני קטעים שונים יהיה חיתוך באורך אפס. מצאו את הסכום המקסימלי האפשרי של אורכי הקטעים, או קבעו שאי אפשר לבחור קטעים המקיימים את התנאי.
קלט
השורה הראשונה מכילה מספר שלם אחד $n$ — מספר השלשות. $n$ השורות הבאות מכילות שלושה מספרים שלמים $a_i$, $b_i$ ו-$c_i$ — השלשה ה-$i$.
פלט
אם אי אפשר ליצור קטעים המקיימים את התנאי, הדפיסו -1. אחרת, הדפיסו את הסכום המקסימלי האפשרי של אורכי הקטעים.
מגבלות
$1 \le n \le 10^6$, $1 \le a_i < b_i < c_i \le 10^9$.
דוגמאות
קלט 1
4 1 2 3 2 3 5 7 8 9 4 7 8
פלט 1
7
קלט 2
3 1 2 4 1 2 4 1 2 4
פלט 2
-1
הערה
בדוגמה הראשונה, ישנן $n = 4$ שלשות: $(1, 2, 3)$, $(2, 3, 5)$, $(7, 8, 9)$ ו-$(4, 7, 8)$. פתרון אופטימלי אחד הוא: $(1, 2)$, $(2, 3)$, $(7, 9)$, $(4, 7)$. קטעים אלה מקיימים את התנאי שלכל שני קטעים שונים יש חיתוך באורך אפס. סכום אורכיהם הוא $(2 - 1) + (3 - 2) + (9 - 7) + (7 - 4) = 1 + 1 + 2 + 3 = 7$. בדוגמה השנייה, אי אפשר לבחור את הקטעים כך שיקיימו את התנאי.