Τα ζώα του Βυθού, φημισμένα για την τεχνογνωσία τους, ανακάλυψαν στα προηγμένα εργαστήριά τους μία πραγματική χρονομηχανή, δηλαδή μια μηχανή που τους μεταφέρει στο μέλλον ή στο παρελθόν. Δυστυχώς όμως, η νέα αυτή τεχνολογία είναι σε πρώιμο στάδιο και ο χρήστης της μηχανής δεν μπορεί να μεταβεί σε οποιαδήποτε χρονική στιγμή θέλει χωρίς περιορισμούς.
Η χρονομηχανή χρησιμοποιεί ως καύσιμο κοράλια, τα οποία ο χρήστης θα πρέπει να αγοράσει από ειδικό μαγαζί του Βυθού. Κάθε κοράλι έχει μία τιμή, η οποία δηλώνει πόσες μέρες θα τον μεταφέρει στο χρόνο. Αυτή η τιμή λέγεται διάρκεια του κοραλιού. Στη μηχανή υπάρχουν δύο υποδοχές κοραλιών, μία για το μέλλον και μία για το παρελθόν και μπορούν να εισαχθούν στην κάθε μία οποιαδήποτε και οσαδήποτε κοράλια. Συγκεκριμένα αν κάποιος βάλει ένα κοράλι με διάρκεια x στην υποδοχή του μέλλοντος, θα μεταφερθεί x ημέρες μπροστά στο μέλλον, ενώ αν το βάλει στην υποδοχή του παρελθόντος, θα μεταφερθεί x ημέρες πίσω στο παρελθόν. Φυσικά κάθε κοράλι μπορεί να χρησιμοποιηθεί το πολύ μία φορά.
Ο Μίλτος θέλει να χρησιμοποιήσει αυτή τη μηχανή για να μεταφερθεί Χ ημέρες μπροστά στο μέλλον και για να το πετύχει αυτό πρέπει να αγοράσει μερικά κοράλια. Υπάρχουν Ν κοράλια διαθέσιμα προς αγορά, το i-οστό από τα οποία έχει διάρκεια Α[i]. Σαν να μην έφταναν τα προβλήματα του Μίλτου, ο πωλητής των κοραλιών αποφάσισε ότι για κάθε δύο κοράλια με διάρκειες x και y με x<y που θα αγοράσει ο Μίλτος, θα πρέπει να αγοράσει και όλα τα κοράλια με ενδιάμεσες διάρκειες, δηλαδή όλα τα διαθέσιμα κοράλια με διάρκεια z τέτοια ώστε x<z<y. Όλα τα κοράλια έχουν το ίδιο κόστος, ίσο με 1 νόμισμα. Βοηθήστε το Μίλτο, βρίσκοντας τα ελάχιστα νομίσματα που θα πρέπει να δώσει, έτσι ώστε να μεταφερθεί Χ μέρες στο μέλλον. Σημ: Προφανώς δεν είναι πάντα αναγκαίο να χρησιμοποιήσει όλα τα κοράλια τα οποία αγόρασε.
Στην πρώτη γραμμή της εισόδου θα περιέχονται 2 θετικοί ακέραιοι, οι N και X, χωρισμένοι από ένα κενό. Στην επόμενη γραμμή δίνονται οι θετικοί ακέραιοι A[i], οι διάρκειες των διαθέσιμων κοραλιών.
Στην έξοδο πρέπει να περιέχονται δύο ακέραιοι χωρισμένοι με κενό. Ο πρώτος θα είναι το ελάχιστο πλήθος νομισμάτων που θα χρειαστεί ο Μίλτος για να πετύχει το στόχο του και ο δεύτερος η διάρκεια του κοραλιού που είχε τη μέγιστη διάρκεια από αυτά που αγόρασε. Αν υπάρχουν πολλαπλές λύσεις με ελάχιστο πλήθος νομισμάτων, να τυπώσετε αυτήν με την ελάχιστη διάρκεια του μέγιστου κοραλιού, δηλαδή με ελάχιστο το δεύτερο ακέραιο που θα τυπωθεί. Αν δεν υπάρχει λύση να τυπώσετε απλά -1. (Πάντα αλλαγή γραμμής στο τέλος)
0<N<=50
0<X<=50000
0<A[i]<=1000
Επιπλέον:
Για 60% των αρχείων ελέγχου, N<=30 και sum{A[i]}<=15000
Για 30% των αρχείων ελέγχου, N<=15 και χρειάζονται το πολύ 5 νομίσματα.
5 11 5 2 8 13 10
3 8
Ο Μίλτος θέλει να μεταφερθεί 11 μέρες στο μέλλον και υπάρχουν διαθέσιμα κοράλια με διάρκειες 5, 2, 8, 13 και 10.
Θα αγοράσει τα κοράλια 5, 2 και 8. Δεν υπάρχουν ενδιάμεσα διαθέσιμα κοράλια άρα δεν θα χρειαστεί να αγοράσει κάτι άλλο. Θα βάλει στην υποδοχή του μέλλοντος τα κοράλια 5 και 8, και στην υποδοχή του παρελθόντος το κοράλι 2, άρα συνολικά θα μεταφερθεί +5+8-2 = +11 μέρες. Θα χρειαστεί 3 νομίσματα και το μέγιστο κοράλι που αγόρασε έχει διάρκεια 8.
Εναλλακτικά, θα μπορούσε να αγοράσει τα κοράλια 8, 10 και 13, βάζοντας στην υποδοχή του μέλλοντος τα 8 και 13 και στην υποδοχή του παρελθόντος το 10, άρα θα μεταφερθεί +8+13-10=+11 μέρες. Θα χρειαστεί 3 νομίσματα και το μέγιστο κοράλι που θα αγοράσει θα έχει διάρκεια 13. (Στην προηγούμενη λύση το μέγιστο κοράλι έχει διάρκεια 8<13, γι’ αυτό και επιλέγουμε εκείνη)
Μία άλλη ιδέα θα ήταν να χρησιμοποιήσει τα κοράλια 2 και 13, βάζοντας το 13 στην υποδοχή του μέλλοντος και το 2 στην υποδοχή του παρελθόντος. Τότε θα είχε μεταφερθεί +13-2=+11 μέρες. Λόγω του περιορισμού του πωλητή όμως, επειδή 2<5<13, 2<8<13 και 2<10<13 θα έπρεπε να αγοράσει και τα κοράλια 5, 8 και 10. Άρα θα χρειαζόταν 5 νομίσματα, το οποίο δεν είναι το ελάχιστο.