5. Krvilačný súboj planét

Ak nevieš programovať, nezúfaj! Môžeš sa to naučiť a ešte za to získať body, ktoré sa ti budú počítať namiesto tejto úlohy. Stačí, že pôjdeš na stránku nášho testovača a budeš riešiť sadu Úvod do programovania. Každou z úloh Najmenší, Akéže je znamienko?, Prostredný si vieš nahradiť 5 bodov z tejto úlohy. Pomôcť si vieš Python tutoriálom, ktorý sme pre teba nachystali. Stačí ak na spodku tejto stránky odovzdáš pdf-ko s prezývkou, ktorú používaš na testovači.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Krtkovi na [email protected]

Včera sa stalo niečo neslýchané! Niečo, čo bude mať katastrofálne následky! A ostáva nám len dúfať, že to neovplyvní našu časť vesmíru.

Ešte predvčerom pokojní obyvatelia planéty Sysľov lietali na ufách krížom krážom galaxiou, zúčastňovali sa všetkých možných programátorských súťaží a všetky do jednej vyhrávali. Včera však utrpeli strašnú porážku, prvýkrát v histórii, a to práve od obyvateľov planéty Žiab. Aby si zachovali česť, neostáva im nič iné, ako planéte Žiab vyhlásiť vojnu. Nie programátorskú, tam si už nie sú takí istí, ale fyzickú a likvidačnú.

V skratke, v neďalekom vesmíre vypukol Krvilačný Súboj Planét.

Najdôležitejším krokom vo vojne je produkcia bojových robotov. Syslí návrhári vytvorili prototyp, na základe ktorého sa budú stavať. Pri stavbe robota sa však využívajú niektoré prototypom definované suroviny, ktorých je len obmedzene veľa, obmedzený je teda aj počet robotov, ktorých vedia vyrobiť.

Na planéte Sysľov sa však nachádza aj jedna špeciálna surovina – žolícium. Tá sa vyznačuje tým, že sa ňou dá nahradiť ľubovoľná iná surovina. Z dostatku žolícia dokonca môžete postaviť celého robota. Ak sa teda žolícium správne prerozdelí medzi zvyšné suroviny, môže sa zvýšiť počet robotov, ktorých vedia na planéte Sysľov vytvoriť. Obyvatelia planéty Sysľov však nevedia, ako žolícium rozdeliť a naprogramovať si to už netrúfajú.

Úloha

Dostanete cenu jedného robota vyjadrenú ako počet jednotlivých surovín, ktoré na jeho výrobu treba. Okrem toho dostanete aktuálny počet každej zo surovín a počet špeciálnej suroviny, žolícia, ktoré môže byť použité ako ľubovoľná surovina. Riešiť potom musíte dva typy úloh: * Obrana – dostanete navyše počet robotov, ktorý by sme chceli vytvoriť a vašou úlohou je zistiť, či sa daný počet da vytvoriť zo zadaných surovín. * Útok – zistite maximálny možný počet robotov, ktorých vieme poskladať zo zadaných surovín.

Ak viete vyriešiť iba jednu z podúloh, nezúfajte, určite sa vám újdu nejaké body.

Formát vstupu

Na prvom riadku vstupu je jedno slovo, a to Obrana alebo Utok, podľa toho, či teraz treba brániť alebo útočiť.

Na druhom riadku vstupu sú dve čísla, \(n\) \((1 \leq n \leq 10^5)\) – počet rôznych typov surovín, a \(b\) \((0 \leq b \leq 10^{14})\) – počet špeciálnych surovín, ktoré môžete rozdeliť ako chcete.

Na treťom riadku vstupu je \(n\) čísel, \(i\)-te z nich znamená, že máte k dispozícií \(A_i\) \((0 \leq A_i \leq 10^{7})\) \(i\)-teho typu surovín.

Na štvrtom riadku vstupu je \(n\) čísel, \(i\)-te z nich znamená, že počet potrebných surovín \(i\)-teho typu na jedného robota je \(B_i\) \((0 \leq B_i \leq 10^{6})\). Navyše máte garantované, robot stojí aspoň \(1\) z nejakej suroviny.

Ak sa jedná o obranu, vstup má ešte jeden riadok, na ňom je jedno kladné celé číslo – počet robotov, ktorých treba vyrobiť, aby sme sa ubránili.

Navyše platí, že bez ohľadu nato, či sa Sysľovčania bránia alebo útočia, nemôžu vyrobiť viac robotov ako počet atómov na planéte Sysľov, teda viac ako \(10^{10}\) robotov.

Formát výstupu

Ak sa jedná o útok, vypíšte jedno číslo – najväčší počet robotov, ktoré môžeme vyrobiť.

Ak sa jedná o obranu, vypíšte Ano, ak sa daný počet robotov dá postaviť, a Nie ak sa nedá.

Hodnotenie

Je 5 sád vstupov a za každú je možné získať 3 body.

Navyše platí, že v druhej sade sú len obrany.

Upozornenie: Počet vyrobených robotov aj počty surovín môžu byť veľmi veľké čísla. Preto si treba uvedomiť, že v niektorých jazykoch majú bežné celočíselné premenné obmedzený rozsah. Napríklad v C++ int má klasicky 32 bitov, čo nemusí stačiť. Chcete preto použiť 64 bitové premenné (napr. long long v C++, Int64 v Pascale).

Príklad

Input:

Utok
9 15
6 8 3 7 7 4 9 4 5
1 2 4 2 4 4 2 4 1

Output:

2

Ak si pridáme 5 z druhého typu, 1 z štvrtého typu a 4 z piateho typu a 4 zo siedmeho typu, budeme mať dostatok na 2 robotov. Ak by sme chceli vyrobiť 3, potrebovali by sme pridať aspoň 9 druhého typu, a 8 z piateho typu. Bohužiaľ máme iba 15 bonusových surovín

Input:

Obrana
9 15
6 8 3 7 7 4 9 4 5
1 2 4 2 4 4 2 4 1
3

Output:

Nie