Fun Palace

Εργάζεστε σκληρά για να προετοιμάσετε ένα διασκεδαστικό πάρτι για τους διασκεδαστικούς φίλους σας. Ευτυχώς, μόλις εντοπίσατε τον τέλειο χώρο για το διασκεδαστικό πάρτι: ένα διασκεδαστικό παλάτι. Το διασκεδαστικό παλάτι έχει ~N~ δωμάτια διασκέδασης που συνδέονται σε μία γραμμική δομή. Τα δωμάτια διασκέδασης αριθμούνται από το ~1~ έως το ~N~ , και για ~1~ ~\le~ ~i~ ~\le~ ~N~ - ~1~, τα δωμάτια διασκέδασης ~i~ και ~i~ + ~1~ συνδέονται με ένα διασκεδαστικό τούνελ. Λέμε ότι ένα τέτοιο διασκεδαστικό τούνελ είναι προσπίπτων στα δωμάτια διασκέδασης ~i~ και ~i~ + ~1~. Επιπλέον, το δωμάτιο διασκέδασης ~1~ προσπίπτει σε μια σήραγγα εξόδου που φεύγει από το παλάτι διασκέδασης.

Τα διασκεδαστικά τούνελ μπορούν να βρίσκονται σε μία από δύο καταστάσεις: ανοιχτά ή κλειστά. Όταν το διασκεδαστικό τούνελ μεταξύ των δωματίων διασκέδασης ~i~ και ~i~ + ~1~ είναι ανοιχτό, οι διασκεδαστικοί φίλοι μπορούν να ταξιδεύουν ελεύθερα μεταξύ των δύο δωματίων, σε οποιαδήποτε κατεύθυνση.

Από προεπιλογή, τα διασκεδαστικά τούνελ θα είναι όλα κλειστά. Ωστόσο, ενδέχεται να ανοίξουν προσωρινά από μια ομάδα διασκεδαστικών φίλων που πατούν τον απαιτούμενο αριθμό κουμπιών διασκέδασης. Για κάθε διασκεδαστικό τούνελ, υπάρχει ένα σύνολο από κουμπιά διασκέδασης που υπάρχουν στα δωμάτια διασκέδασης που συνδέονται με το τούνελ διασκέδασης. Αν όλα τα κουμπιά σε ένα από τα δωμάτια που συνδέονται με ένα τούνελ πιέζονται προς τα κάτω από διακριτούς διασκεδαστικούς φίλους τότε το διασκεδαστικό τούνελ θα ανοίξει. Διαφορετικά, το διασκεδαστικό τούνελ θα κλείσει αμέσως. Το διασκεδαστικό τούνελ μεταξύ των δωματίων ~i~ και ~i~ + ~1~ συνδέεται με ένα σύνολο κουμπιών ~a_i~ στο δωμάτιο ~i~ και με ένα σύνολο κουμπιών ~b_i~ στο δωμάτιο ~i~ + ~1~. Για να το θέσουμε αλλιώς, αν υπάρχουν τουλάχιστον ~a_i~ φίλοι στο δωμάτιο ~i~ ή αν υπάρχουν ~b_i~ φίλοι στο δωμάτιο ~i~ + ~1~, τότε μπορεί να ανοίξει το τούνελ μεταξύ του δωματίου ~i~ και ~i~ + ~1~.

Το τούνελ εξόδου λειτουργεί με παρόμοιους κανόνες, αλλά συνδέεται με ένα μόνο σύνολο από ~e~ κουμπιά που βρίσκονται στο δωμάτιο ~1~.

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

Είσοδος

Η πρώτη γραμμή θα περιέχει έναν μόνο ακέραιο ~N~ (~1~ ~\le~ ~N~ ~\le~ ~1\,000~), τον αριθμό των δωματίων διασκέδασης. Η επόμενη γραμμή περιέχει έναν μόνο ακέραιο ~e~ (~1~ ~\le~ ~e~ ~\le~ ~10\,000~). Οι επόμενες ~N~-~1~ γραμμές περιέχουν δύο, χωρισμένους με κενό, ακέραιους η καθεμία, με την ~i~-οστη από αυτές τις γραμμές να περιέχει το ~a_i~ και ~b_i~ (~1~ ~\le~ ~a_i~, ~b_i~ ~\le~ ~10\,000~).

Βαθμολογία

Για ~3~ από τους ~25~ διαθέσιμους βαθμούς, ~1~ ~\le~ ~e~ ~\le~ 200~, ~a_i~ = ~1~, ~b_i~ = ~1~.

Για επιπλέον ~5~ από τους ~25~ διαθέσιμους βαθμούς, ~1~ ~\le~ ~e~, ~a_i~, ~b_i~ ~\le~ ~2~.

Για επιπλέον ~12~ από τους ~25~ διαθέσιμους βαθμούς, ~N~ ~\le~ ~200~, ~1~ ~\le~ ~e~, ~a_i~, ~b_i~ ~\le~ ~200~.

Έξοδος

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

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

input

2
20
5 5

output

19

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

Αν είχαμε πάνω από ~19~ διασκεδαστικούς φίλους, θα μπορούσαν να μετακινηθούν στο δωμάτιο διασκέδασης ~1~ και να πατήσουν και τα ~20~ κουμπιά που απαιτούνται για να ανοίζει το τούνελ εξόδου.

input

2
20
5 20

output

24

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

Υποθέστε ότι τοποθετούμε ~24~ διασκεδαστικούς φίλους στο δωμάτιο διασκέδασης ~2~. Για να μπορέσουν να ανοίξουν το διασκεδαστικό τούνελ μεταξύ των δωματίων ~1~ και ~2~, ~20~ φίλοι πρέπει να μείνουν στο δωμάτιο ~2~ για να πατήσουν τα κουμπιά. Αυτό επιτρέπει μόνο ~4~ φίλους στο δωμάτιο ~1~, οι οποίοι δεν είναι αρκετοί για να πατήσουν κάθε κουμπί στο σύνολο από ~5~ κουμπιά.

input

7
7
2 8
6 6
1 1
2 4
2 8
7 8

output

23

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

Μία βέλτιστη κατανομή είναι να τοποθετήσουμε ~9~ διασκεδαστικούς φίλους στο δωμάτιο διασκέδασης ~2~ και ~14~ φίλους στο δωμάτιο ~7~.