Roboter im Einsatz
In der Fabrik gibt es
n Roboter. Da die einzelnen Roboter unterschiedlichen Generationen angehören, benötigen sie für die Produktion desselben Produkts unterschiedlich viel Zeit. Neuere Roboter arbeiten schneller, ältere sind langsamer. Alle Roboter können gleichzeitig eingesetzt werden. Die Fabrik muss X Produkte herstellen. Als Leiter der Fabrik wird man gebeten, die kürzestmögliche Zeit zu ermitteln, um diese X Produkte zu produzieren.Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen
n (1 ≤ n ≤ ) und X (1 ≤ X ≤ ).In der nächsten Zeile folgen
n ganze Zahlen , durch Leerzeichen getrennt. Jede dieser Zahlen gibt an, wie viel Zeit der jeweilige Roboter benötigt, um ein Produkt herzustellen (1 ≤ ≤ ).Ausgabe
Das Programm soll die minimale benötigte Zeit ausgeben, innerhalb der
X Produkte gefertigt werden können.Beispiele
Eingabe | Ausgabe |
3 8
4 2 5 | 10 |
Erklärung
- Die erste Maschine stellt 2 Produkte her (time=8), die zweite Maschine 5 Produkte (time=10) und die dritte 1 Produkt (time=5) ⇒ Insgesamt 10 Produkte.
- Die erste Maschine stellt 2 Produkte her (time=8), die zweite Maschine 4 Produkte (time=8) und die dritte 2 Produkte (time=10) ⇒ Insgesamt 10 Produkte.
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB