Ο χειμώνας έρχεται και τα ζώα ψάχνουν τροφή για τις κρύες μέρες που έρχονται. Ένας σκαντζόχοιρος έχει προμηθευτεί μία μεγάλη βαλίτσα, μέσα στην οποία μπορεί να μεταφέρει τα φαγητά που βρίσκει στο δάσος. Συγκεκριμένα, έχει εντοπίσει Ν διαφορετικές μουριές μέσα στο δάσος, από τις οποίες θα πάρει την τροφή που χρειάζεται για το χειμώνα. Η i-οστή από αυτές τις μουριές έχει A[i] μούρα. Ο σκαντζόχοιρος κάθε μέρα μπορεί να κάνει μία από τις παρακάτω κινήσεις:
-Να βάλει όλα τα μούρα της i-οστής μουριάς μέσα στη βαλίτσα του, υπό την προϋπόθεση ότι χωράνε σε αυτήν και ότι μέσα στη βαλίτσα δεν υπάρχουν ήδη μούρα από 2 διαφορετικές μουριές (Με άλλα λόγια, η βαλίτσα σε μία στιγμή μπορεί να περιέχει τους καρπούς το πολύ 2 διαφορετικών μουριών).
-Να αδειάσει όλο το περιεχόμενο της βαλίτσας στη φωλιά του, όπου αποθηκεύει το φαγητό του.
Κάθε μέρα γίνεται το πολύ μία από τις παραπάνω δύο κινήσεις. Γνωρίζουμε ότι του χρειάστηκαν Κ ημέρες μέχρι να καταφέρει να μαζέψει όλα τα μούρα από όλες τις μουριές στη φωλιά του. Ποιος είναι ο ελάχιστος αριθμός από μούρα που μπορεί να χωράει η βαλίτσα του; Αν δεν μπορεί να μαζέψει όλα τα μούρα, τότε τυπώστε -1.
Στην πρώτη γραμμή περιέχονται δύο ακέραιοι, Ν και K, το πλήθος των διαφορετικών μουριών και το πλήθος των ημερών που χρειάστηκε ο σκαντζόχοιρος, αντίστοιχα. Στην επόμενη γραμμή περιέχονται Ν ακέραιοι χωρισμένοι μεταξύ τους με κενά, ο i-οστός από τους οποίους αντιστοιχεί στο πόσα μούρα έχει η i-οστή μουριά (A[i]).
Στην έξοδο θα πρέπει να τυπώνεται ένας ακέραιος, το ελάχιστο πλήθος μούρων που μπορεί να χωράει η βαλίτσα του σκαντζόχοιρου, ή -1 αν δεν μπορεί να μαζέψει όλα τα μούρα στη φωλιά του.
1 <= N <= 100.000
1 <= K <= 200.000
1 <= A[i] <= 1.000.000.000
3 5 2 4 3
5
Αν έχουμε μέγεθος βαλίτσας μικρότερο από 5, τότε θα χρειαστούν τουλάχιστον 6 ημέρες.
Από την άλλη, αν έχουμε μέγεθος ίσο με 5, μπορούμε να κάνουμε τα εξής:
1η μέρα: Βάζουμε τα 2 μούρα στη βαλίτσα.
2η μέρα: Βάζουμε τα 3 μούρα στη βαλίτσα.
3η μέρα: Αδειάζουμε τη βαλίτσα.
4η μέρα: Βάζουμε τα 4 μούρα στη βαλίτσα.
5η μέρα: Αδειάζουμε τη βαλίτσα.
Συνεπώς η μικρότερη χωρητικότητα που μπορεί να έχει η βαλίτσα είναι 5 μούρα.