Όμοιες Πίτσες

Σας παρουσιάζουμε τον πρωταγωνιστή μας τον Τάκη, έναν νεαρό Έλληνα που το όνειρό του από μικρό παιδί είναι να ανοίξει την δική του πιτσαρία. Σήμερα, βρίσκεται πολύ κοντά στο να κάνει αυτό το όνειρό του πραγματικότητα.

Για να εξοικονομήσει όσο γίνεται περισσότερα χρήματα, το πλάνο του Τάκη είναι να μην προσλάβει προσωπικό, αλλά να φτιάχνει και να σερβίρει ο ίδιος τις πίτσες του. Στην αποθήκη του διαθέτει ~N~ υλικά. Οι ποσότητες των διάφορων υλικών συμβολίζονται με τους θετικούς ακέραιους ~a_1~, ~a_2~, ~...~, ~a_N~. Ο σκοπός του Τάκη είναι να δημιουργήσει όσο το δυνατόν περισσότερες όμοιες πίτσες μπορεί. Λέμε ότι κάποιες πίτσες είναι όμοιες όταν όλες:

• αποτελούνται από τα ίδια υλικά και
• διαθέτουν την ίδια (θετική ακέραια) ποσότητα από καθένα από αυτά τα υλικά.

Προκειμένου οι πίτσες του να μην είναι "βαρετές", ο Τάκης έθεσε ακόμα έναν περιορισμό: πρέπει κάθε πίτσα να περιέχει τουλάχιστον ~K~ διαφορετικά υλικά. Να υπολογίσετε ποιο είναι το μέγιστο πλήθος από όμοιες πίτσες που μπορεί να δημιουργήσει ο Τάκης, τηρώντας ταυτόχρονα αυτόν τον περιορισμό.

Πρόβλημα

Να γράψετε ένα πρόγραμμα σε μία από τις γλώσσες του ΠΔΠ (PASCAL, C, C++, JAVA) το οποίο θα διαβάζει τα δεδομένα εισόδου από το αρχείο samepizzas.in και θα εκτυπώνει τα αποτελέσματα στο αρχείο samepizzas.out.

Αρχεία εισόδου (samepizzas.in)

Η πρώτη γραμμή περιέχει τον αριθμό του υποπροβλήματος (βλ. παρακάτω). Η δεύτερη γραμμή περιέχει δύο ακέραιους αριθμούς ~N~ και ~K~, χωρισμένους μεταξύ τους με ένα κενό διάστημα: το πλήθος των υλικών που διαθέτει ο Τάκης και το ελάχιστο δυνατό πλήθος διαφορετικών υλικών που μπορεί να περιέχει κάθε πίτσα του. Η τρίτη γραμμή αποτελείται από ~N~ ακέραιους αριθμούς ~a_1~, ~a_2~, ~...~, ~a_N~, χωρισμένους ανά δύο με κενό διάστημα: τις ποσότητες των υλικών.

Αρχεία εξόδου (samepizzas.out)

Πρέπει να περιέχει μία μόνο γραμμή με έναν ακέραιο αριθμό: το μέγιστο πλήθος από όμοιες πίτσες που μπορεί να δημιουργήσει ο Τάκης πληρώντας τον παραπάνω περιορισμό.

Παράδειγμα αρχείων εισόδου - εξόδου:

Είσοδος:

4
5 3
12 6 7 6 4

Έξοδος:

6

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

Περιορισμοί

• ~1 \le K \le N \le 200.000~
• ~1 \le a_i \le 1.000.000.000~

Υποπροβλήματα:

1. (10 βαθμοί) ~N = 2~
2. (15 βαθμοί) ~K = N~
3. (25 βαθμοί) ~K = 1~
4. (10 βαθμοί) ~N \le 10.000~
5. (40 βαθμοί) Δεν υπάρχουν περαιτέρω περιορισμοί

Παρατηρήσεις:

• Μορφοποίηση: Στην είσοδο αλλά και στην έξοδο, κάθε γραμμή τερματίζει με έναν χαρακτήρα newline.
• Μέγιστος χρόνος εκτέλεσης: ~1~ sec.
• Μέγιστη διαθέσιμη μνήμη: ~64~ MB.
• Επικεφαλίδες στον πηγαίο κώδικα: Στην αρχή του πηγαίου κώδικά σας, θα πρέπει να χρησιμοποιήσετε τις παρακάτω επικεφαλίδες.

(* USER: username
LANG: PASCAL
TASK: samepizzas *)

για κώδικα σε PASCAL

/* USER: username
LANG: C
TASK: samepizzas */

για κώδικα σε C

/* USER: username
LANG: C++
TASK: samepizzas */

για κώδικα σε C++

/* USER: username
LANG: Java
TASK: samepizzas */

για κώδικα σε Java

Προσοχή: Η απάντηση μπορεί να υπερβαίνει το ~2^{32}~. Επίσης, φροντίστε να διαβάζετε την είσοδο και να εκτυπώνετε την έξοδο αποδοτικά, ειδικά αν μεταφράζετε σε C++ ή Java.