Lazy Fox

Έχετε για κατοικίδιο μια αλεπού που λατρεύει τις λιχουδιές. Έχετε ~N~ γείτονες σε διαφορετικές τοποθεσίες (που περιγράφονται ως σημεία στο καρτεσιανό επίπεδο), οι οποίοι προσφέρουν λιχουδιές στην αλεπού σας, και κάθε γείτονας έχει απεριόριστο αριθμό λιχουδιών να δώσει. Η αφετηρία (από όπου ξεκινάει η αλεπού για να πάρει λιχουδιές) δεν θα είναι μία από αυτές τις ~N~ τοποθεσίες.

Τι λέει η αλεπού, προκειμένου να πάρει αυτές τις λιχουδιές; Αυτή είναι μια καλή ερώτηση, αλλά δεν μας αφορά.

Η αλεπού μετακινείται από τοποθεσία σε τοποθεσία για να συλλέξει ακριβώς μία λιχουδιά από κάθε τοποθεσία σε κάθε επίσκεψη. Μπορεί να επισκεφθεί ξανά οποιαδήποτε προηγούμενη τοποθεσία, αλλά δεν μπορεί να επισκεφθεί την ίδια τοποθεσία σε δύο διαδοχικές επισκέψεις.

Η αλεπού σας είναι πολύ τεμπέλα. Η απόσταση που είναι πρόθυμη να διανύσει η αλεπού σας μετά από κάθε λιχουδιά θα μειώνεται γνησίως. Συγκεκριμένα, η απόσταση από την αφετηρία μέχρι την πρώτη τοποθεσία λιχουδιάς πρέπει να είναι μεγαλύτερη από την απόσταση από την πρώτη τοποθεσία λιχουδιάς στη δεύτερη τοποθεσία που η αλεπού θα πάρει μια λιχουδιά, η οποία με τη σειρά της είναι μεγαλύτερη από την απόσταση μεταξύ της δεύτερης τοποθεσίας λιχουδιάς και της τρίτης τοποθεσίας λιχουδιάς, και ούτω καθεξής.

Ποιος είναι ο μεγαλύτερος αριθμός λιχουδιών που συγκεντρώνει η αλεπού σας;

Είσοδος

Η πρώτη γραμμή περιέχει τον ακέραιο αριθμό ~N\;(1 \le N \le 2000)~. Οι επόμενες ~N~ γραμμές περιέχουν η καθεμιά τον ~X_{i}~, ακολουθούμενο από ένα κενό, ακολουθούμενο από τον ~Y_{i}~, για ~i = 1..N\;(-10000 \le X_{i},\;Y_{i} \le 10000)~ που αντιπροσωπεύουν τις συντεταγμένες της ~i~-οστής τοποθεσίας. Θα ισχύουν οι ακόλουθοι πρόσθετοι περιορισμοί.

• Τουλάχιστον το ~20%~ των βαθμών θα αφορά αρχέια ελέγχου όπου ~N \le 50~,
• Τουλάχιστον το ~40%~ των βαθμών θα αφορά αρχέια ελέγχου όπου ~N \le 200~,
• οι υπόλοιποι βαθμοί θα αφορούν αρχέια ελέγχου όπου ~N \le 2000~.

Έξοδος

Η έξοδος θα είναι ένας ακέραιος αριθμός, ο μεγαλύτερος αριθμός λιχουδιών που μπορεί να συγκεντρώσει η αλεπού σας.

Παράδειγμα

input

5
5 8
4 10
3 1
3 2
3 3

output

6

Επεξήγηση του παραδείγματος:

Η αλεπού πραγματοποιεί τις επισκέψεις με την ακόλουθη σειρά (με τις υποδεικνυόμενες αποστάσεις):

• ~(0,\;0)~ προς ~(4,\;10)~ με απόσταση ~\sqrt[]{116}~,
• ~(4,\;10)~ προς ~(3,\;1)~ με απόσταση ~\sqrt[]{82}~,
• ~(3,\;1)~ προς ~(5,\;8)~ με απόσταση ~\sqrt[]{53}~,
• ~(5,\;8)~ προς ~(3,\;3)~ με απόσταση ~\sqrt[]{29}~,
• ~(3,\;3)~ προς ~(3,\;1)~ με απόσταση ~2~,
• ~(3,\;1)~ προς ~(3,\;2)~ με απόσταση ~1~.