Zadanie
Jožko je na nákupe v Bille. Treba dokúpiť Horalky, mlieko, zopár nanukov na zlepšenie nálady, a plno ďalších vecí.
Cifra \(3\) je Jožkova obľúbená. Vždy ho poteší keď ju niekde uvidí. Ach tie ladné krivky. Jožko by bol rád ak sa na bločku ktorý mu vydajú bude nachádzať čo najviac krát.
Úloha
Billa predáva \(n\) typov produktov. Produktu typu \(i\) má už Jožko v košíku \(a_i\) kusov, pričom jeden kus stojí \(c_i\) eur.
Do košíka sa mu zmestí už len \(k\) ďalších predmetov. Z ktorých typov produktov si má prikúpiť, aby mal po zaplatení na bločku čo najviac trojok? Môže prihodiť aj menej ako \(k\) predmetov.
Formát vstupu
Na prvom riadku sú dve čísla, \(n\) a \(k\), počet typov produktov, a na koľko kusov má Jožko ešte miesto v košíku. Platí \(1 \leq n,k \leq 10\).
Na druhom riadku sú medzerou oddelené celé čísla \(c_1\) až \(c_n\), ceny jednotlivých typov produktov. Platí \(1 \leq c_i \leq 10^{15}\). Tieto čísla sa vám nebudú zmestiť do 32 bitových číselných premenných (v C++ použite long long
).
Na treťom riadku sú medzerou oddelené celé čísla \(a_1\) až \(a_n\). Jožko má \(a_i\) kusov produktu \(i\) v košíku. Platí \(0 \leq a_i \leq 10\).
Formát výstupu
Vypíšte jedno číslo, najväčší počet výskytov cifry \(3\) aký vie Jožko na svojom bločku dosiahnuť.
Príklady
Input:
3 3
20 15 7
10 3 3
Output:
2
Je možné dosiahnuť dve trojky dokonca dvoma spôsobmi: \(20\cdot 10 + 15\cdot 5 + 7\cdot 4 = 303\) a \(20\cdot 12 + 15\cdot 3 + 7\cdot 4 = 313\)
Input:
4 5
115 61 80 104
8 10 9 7
Output:
4
\(115\cdot 9+61\cdot 10+80\cdot 12+104\cdot 7=3333\)
HTML vzorák nie je k dispozícii.
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.