Počet bodov:
Popis:  12b
Program:  8b

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\)\(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_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\)

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.