Τι λέτε για την παρακάτω άσκηση?
είναι από το hellenico, από το διαγωνισμό Ιανουαρίου
Εκφώνηση
Ο Μίλτος το δελφίνι αποφάσισε με τη νέα χρονιά να προσέξει τη διατροφή του, να σταματήσει το fast food και να αρχίσει να τρώει μόνο φρούτα, για να είναι σε φόρμα για τους αγώνες στίβου που γίνονται Βυθό. Έτσι, επισκέφθηκε το super market της γειτονιάς του για να αγοράσει πάρα πολλά φρούτα. Μόλις έφτασε εκεί διαπίστωσε ότι υπάρχουν Ν διαφορετικά είδη φρούτων, όπου το i-οστό από αυτά κοστίζει c κοχύλια το κάθε φρούτο και είναι διαθέσιμες συνολικά b μονάδες φρούτων. Ο Μίλτος ετοιμάζεται να τα αγοράσει όλα, όμως ο υπάλληλος τον σταματάει, περιγράφοντάς του την περίεργη πολιτική του μαγαζιού όσον αφορά τις αγορές φρούτων. Θα πρέπει για τα φρούτα που θα αγοράσει να ισχύει το εξής: Αν επιλέξει τυχαία μερικά από αυτά (τουλάχιστον ένα), η πιθανότητα να τα έχει επιλέξει όλα να είναι ακριβώς 1/P, όπου P θετικός ακέραιος. Να βρείτε το ελάχιστο ποσό χρημάτων που απαιτούνται για να αγοράσει ο Μίλτος κάποια φρούτα σύμφωνα με τους περιορισμούς.
Δεδομένα εισόδου (αρχείο "fruit.in")
Στην πρώτη γραμμή δίνονται οι N,P. Σε κάθε μία από τις επόμενες N γραμμές δίνεται η ποσότητα και το κόστος κάποιου από τα Ν είδη φρούτων.
Δεδομένα εξόδου (αρχείο "fruit.out")
Το ελάχιστο κόστος, ή -1 αν δεν γίνεται να αγοράσει τίποτα.
Περιορισμοί
1<=N<=10000
1<=P<=70000
1<=b,c<=70000
Όριο χρόνου εκτέλεσης: 5 sec.
Όριο μνήμης: 64 MB.
