Crazy Fencing

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

Ωστόσο, ο φράχτης είναι κατασκευασμένος από (~N~) ανομοιόμορφα κομμάτια ξύλου και ο γείτονάς σας πιστεύει ότι αυτό του προσδίδει καλλιτεχνική άποψη. Το κάτω μέρος κάθε κομματιού ξύλου είναι οριζόντιο, οι δύο πλευρές του είναι κάθετες, αλλά η κορυφή του μπορεί να είναι κομμένη υπό γωνία. Δύο τέτοια κομμάτια ξύλου παρουσιάζονται παρακάτω:

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

Είσοδος

Η πρώτη γραμμή της εισόδου θα περιέχει έναν θετικό ακέραιο αριθμός ~N~, όπου ~N \le 10000~.

Η δεύτερη γραμμή της εισόδου θα περιέχει ~N + 1~ ακέραιους αριθμούς ~h_{1}~, ~. . .~ , ~h_{N +1}\;(1 \le h_{i} \le 100,\;1 \le i \le N + 1)~, χωρισμένους με κενά διαστήματα, που θα περιγράφουν το αριστερό και το δεξί ύψος κάθε ξύλου. Συγκεκριμένα, το αριστερό ύψος του ~i~-οστού κομματιού ξύλου θα είναι ~h_{i}~ και το δεξί ύψος του ~i~-οστού κομματιού ξύλου θα είναι ~h_{i+1}~.

Η τρίτη γραμμή της εισόδου θα περιέχει ~N~ ακέραιους αριθμούς ~w_{i}\;(1 \le w_{i} \le 100,\;1 \le i \le N)~ που θα περιγράφουν το πλάτος του ~i~-οστού κομματιού ξύλου.

Έξοδος

Εξάγετε το συνολικό εμβαδόν του φράχτη.

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

input

3
2 3 6 2
4 1 1

output

18.5

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

Ο φράχτης έχει την ακόλουθη μορφή:

Κοιτάζοντας από αριστερά προς τα δεξιά, τα επιμέρους εμβαδά των κομματιών ξύλου είναι ~10 = 4 * (2 + 3)/2~, ~4.5 = 1 * (3 + 6)/2~, και ~4 = 1 * (6 + 2)/2~, και προκύπτει συνολικό εμβαδόν ~18.5~.

input

4
6 4 9 7 3
5 2 4 1

output

75

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

Ο φράχτης έχει την ακόλουθη μορφή:

Κοιτάζοντας από αριστερά προς τα δεξιά, τα επιμέρους εμβαδά των κομματιών ξύλου είναι ~25~, ~13~, ~32~ και ~5~ και προκύπτει συνολικό εμβαδόν ~75~.