Suma

Ο Mirko ζει σε ένα μεγάλο μαγεμένο δάσος όπου τα δέντρα είναι πολύ ψηλά και μεγαλώνουν πολύ γρήγορα. Αυτό το δάσος μπορεί να αναπαρασταθεί ως ένας πίνακας ~N \times N~ όπου κάθε πεδίο περιέχει ένα δέντρο.

Ο Mirko αγαπά πολύ τα δέντρα στο μαγεμένο δάσος. Πέρασε χρόνια παρατηρώντας τα και για κάθε δέντρο μέτρησε πόσα μέτρα μεγάλωνε σε ένα χρόνο. Τα δέντρα μεγαλώνουν συνεχώς. Με άλλα λόγια, αν το δέντρο μεγαλώσει 5 μέτρα σε ένα χρόνο, θα μεγαλώσει ~2.5~ μέτρα σε μισό χρόνο.

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

Ο Mirko μέτρησε γρήγορα το τρέχον ύψος όλων των δέντρων στο δάσος και σας ζήτησε να απαντήσετε στην ερώτησή του.

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

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον ακέραιο αριθμό ~N\;(1 \leq N \leq 700)~.

Μετά την πρώτη γραμμή, ακολουθούν ~N~ γραμμές, καθεμία από τις οποίες περιέχει ~N~ ακέραιους αριθμούς.

Η ~i~-οστή γραμμή περιέχει ακέραιους ~h_{ij}\;(1 \leq h_{ij} \leq 10^6)~, το αρχικό ύψος του δέντρου στην ~i~-οστή σειρά και την ~j~-οστή στήλη, σε μέτρα.

Μετά από αυτό, ακολουθούν ~N~ ακόμη γραμμές με ~N~ ακέραιους αριθμούς.

Η ~i~-οστή γραμμή περιέχει ακέραιους ~v_{ij}\;(1 \leq v_{ij} \leq 10^6)~, την ταχύτητα ανάπτυξης του δέντρου στην ~i~-οστή σειρά και την ~j~-οστή στήλη, σε μέτρα.

Προειδοποίηση: Χρησιμοποιήστε πιο γρήγορες μεθόδους εισαγωγής επειδή η ποσότητα της εισόδου είναι πολύ μεγάλη. (Για παράδειγμα, χρησιμοποιήστε scanf αντί για cin στη C++ ή BufferedReader αντί για Scanner σε Java.)

Έξοδος

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

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας ~30~% των συνολικών πόντων, θα έχει ~1 \leq N \leq 70~.

Παραδείγματα

input

3
1 2 3
3 2 2
5 2 1
3 2 1
1 2 1
1 2 3

output

7

input

2
3 1
3 3
2 5
2 5

output

3

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

μετά από 8 μήνες (δύο τρίτα του έτους), τα δέντρα που βρίσκονται στα ~(0,\;0),\;(0,\;1)~ και ~(1,\;0)~ θα έχουν ύψος ~13/3~ μέτρα.