Problem C
Rabatterade rabatter
Varje år planteras det ut massor med nya plantor i rabatterna i en stor park. Än så länge är det för kallt ute för att man ska kunna plantera ut någonting, men Stina håller just på att så växterna i krukor, så de hinner växa sig stora och fina innan det är dags. Hon har varit och storhandlat på Ica-Maxi eftersom de har rabatt på frön. Självfallet köpte hon alla rabatterade blomfrön hon kunde hitta. Hon har sått dessa, men är nu osäker på vilka blomfrön hon ska köpa mer av.
Som tur är vet du exakt vilka växtkombinationer som ser bäst ut enligt parkens besökare! Alla tycker mycket bättre om rabatter där varje plantsort $i$ ($1 \leq i \leq N$) finns $a_ i$ gånger i rabatten. Lyckligtvis har Stina märkt upp vilken sorts planta hon har sått i varje kruka, och går med på att du kan så i resten av krukorna så att så många rabatter som möjligt kan se ut så i vår! (Du får dock inte slänga ut växterna hon har sått eller köpa fler krukor.)
Indata
Den första raden består av två heltal $N$ och $M$, antalet plantsorter som finns och antalet tomma krukor. Den andra raden innehåller $N$ heltal: $a_1, \cdots , a_ N$, antalet blommor av varje sort som behövs för en maximalt omtyckt rabatt. Den tredje raden innehåller $N$ heltal: $b_1, \cdots , b_ N$, antalet frön av varje sort som Stina redan har sått.
Utdata
Det största antalet maximalt omtyckta rabatter som kan skapas när man planterar ut plantorna i alla krukor i vår.
Poängsättning
Din lösning kommer att testas på tre olika testgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
|
Grupp |
Poängvärde |
Begränsningar |
|
1 |
20 |
$1 \leq N \leq 5000$, $0 \leq M \leq 5000$ |
|
och $1<=a_ i,b_ i<=5000$ |
||
|
2 |
30 |
$1 \leq N \leq 10^5$, $M=0$ |
|
och $1 \leq a_ i,b_ i \leq 10^9$ |
||
|
3 |
50 |
$1 \leq N \leq 10^5$, $0 \leq M \leq 10^9$ |
|
och $1 \leq a_ i,b_ i \leq 10^9$ |
Förklaring
I det första exempelfallet kan du först använda de fröna Stina redan har för att fylla tre rabatter. Sedan kan du köpa ett till frö av plantsort 2 och odla i den tomma krukan för att fylla en fjärde rabatt. I det andra exempelfallet kan du köpa ett till frö av sort 1 och två till frön av sort 4 och odla i tre av de tomma krukorna för att få en fin rabatt. Resterande tomma krukor räcker dock inte till för att kunna skapa några fler rabatter och svaret är alltså 1.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 1 2 1 4 11 3 16 |
4 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 10 7 4 6 3 6 8 7 1 |
1 |