Koniec kola: 2. november 2020 23:59
2 dni
Počet bodov:
Popis:  12b
Program:  8b

Leto bolo upršané, rastlinám sa darilo. Zvieratá mali čo pod zub, hovnivály kotúľali. Toľko toho nakotúľali, až nevedia, čo s tým. Je im to ľúto len tak všetko prebytočné spláchnuť do záchoda, alebo nechať do ďalšieho leta splesnivieť. Zhodli sa teda, že potrebujú mrazák. Nie ale iba taký obyčajný. Obrovský. Mnohoposchodový.

Rôzne poschodia ale vyžadujú rôzne veľa času na stavbu. Totiž, v niektorých výškach viac fúka, inde je väčšia zima. Hovniválka Elka letmým pohľadom do vzduchu odhadla, koľko času bude potrebného na postavenie ktorého poschodia mrazáku. Konkrétne zistila, že na postavenie \(i\)-teho poschodia bude potrebného \(c_i\) času.

Hovniválka Elka vie, že ak jeden hovnivál buduje guličku \(m\) minút, tisíc hovniválov postaví guličku za \(m/1000\) minút. To, samozrejme, platí aj o stavbe mrazáku. Ak na \(i\)-tom poschodí bude pracovať \(h_i\) hovniválov, tak toto poschodie dokončia za \(c_i/h_i\) času.

Keďže hovnivál má iba také tenké nožičky, rýchlo sa mu unavia. Každý teda zvládne pomôcť postaviť iba jedno poschodie mrazáku. Poschodie sa ale nedá začať stavať, kým nie je dostavané to predchádzajúce, to predsa dá rozum. Hovniválka Elka chce každého z \(H\) hovniválov poslať na práve jedno poschodnie. Chce to spraviť tak, aby bol celkový čas stavania mrazáku čo najkratší.

Ako najrýchlejšie vedia hovnivály postaviť mrazák?

Úloha

Máme \(H\) hovniválov, ktorí chcú postaviť \(n\)-poschodový mrazák. Hovniválka Elka chce priradiť každému z \(H\) hovniválov nejaké poschodie, na ktorom bude pomáhať so stavbou.

Na každom poschodí, samozrejme, musí pracovať aspoň jeden hovnivál.

Ak je na \(i\)-tom poschodí \(h_i\) hovniválov, stavba \(i\)-teho poschodia zaberie \(c_i/h_i\) času.

Vašou úlohou je zistiť, ako najrýchlejšie vie byť mrazák postavený.

Formát vstupu

Na prvom riadku vstupu sú čísla \(n\) – počet poschodí mrazáku a \(H\) – počet hovniválov. Platí, že \(n \leq H\).

Nasleduje \(n\) riadkov. Na \(i\)-tom z nich je číslo \(c_i\) – základný čas potrebný na stavbu \(i\)-teho poschodia. Platí, že \(1 \leq c_i \leq 100\,000\).

Formát výstupu

Vypíšte jedno číslo – najkratší čas, za ktorý je možné mrazák postaviť.

Vaša odpoveď bude uznaná, ak sa od správnej odpovede nebude odlišovať o viac, ako \(1\).

Hodnotenie

Sú 3 sady vstupov. Platia v nich nasledovné obmedzenia:

Sada 1 2 3, 4
\(1 \leq n \leq\) \(8\) \(100\,000\) \(100\,000\)
\(1 \leq H \leq\) \(20\) \(100\,000\) \(10^{12}\)

Príklad

Input:

3 7
6
2
8

Output:

6.667

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.