Problem B
Kvällsfika

Sara älskar fika! Hon har precis fått $P$ kronor av sin mamma för att köpa lite kvällsfika. Eftersom Sara är smart kommer hon att försöka spendera pengarna så bra som möjligt. I butiken Lugnbyrån finns det $N$ stycken bakelser. Varje bakelse har ett visst pris och en viss kategori. Eftersom Sara gillar fika väldigt mycket så tycker hon nästan att alla sorters bakelser är lika goda. Hon har nämligen ingen preferens för vilken kategori av bakelse hon ska köpa, men hon tycker att det blir lite för enformigt om hon köper fler än $K$ av samma kategori.

Hjälp Sara att köpa så många bakelser som möjligt, vars totala kostnad är mindre än eller lika med $P$. Se dessutom till att det inte finns mer än $K$ bakelser av samma kategori bland de hon köpte. Du behöver endast ange hur många bakelser hon kan köpa, inte vilka.

Indata

Den första raden i indatan innehåller heltalet $N$ ($1 \leq N \leq 10^5$), antalet bakelser som Sara kan välja mellan.

Nästa rad innehåller heltalet $P$ ($1 \leq P \leq 10^8$), antalet kronor som Sara har i budget för kvällsfikat.

Nästa rad innehåller heltalet $K$ ($1 \leq K \leq N$), antalet bakelsetyper som Sara kan tänka sig äta som mest av en specifik.

På nästa rad står heltalen $c_1, c_2, \dots , c_N$ ($1 \leq c_i \leq P$), där $c_i$ betyder att bakelse $i$ kostar $c_i$ kronor. Notera att totala kostnaden av alla bakelser inte nödvändigtvis får plats i ett 32-bitars heltal.

På sista raden står heltalen $t_1, t_2, \dots , t_N$ ($1 \leq t_i \leq 10^5$). Det finns exakt $10^5$ kategorier av bakelser, och vi benämner varje med ett heltal. Talet $t_i$ betyder att bakelse $i$ tillhör kategori $t_i$.

Utdata

Skriv ut ett heltal: antalet bakelser som Sara kan köpa om hon använder sin budget optimalt.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring av exempelfall 1

I detta fallet har Sara råd att köpa alla bakelser, men alla är av samma kategori (kategori 1). Eftersom hon får köpa som mest 2 per kategori kan hon köpa 2 stycken.

Förklaring av exempelfall 2

I detta fallet är kategorier inte ett problem eftersom $K$ är stort, men Sara har inte råd att köpa alla bakelser. Om hon köper bakelserna med pris $4, 3, 2, 1$ har hon precis råd med 4 stycken.

Förklaring av exempelfall 3

En optimal lösning är att köpa bakelser med pris $1,1,4,5$. Här hade Sara kunnat köpa fler bakelser om inte kategorierna begränsade.

3
10
2
2 3 2
1 1 1

2

5
10
5
4 3 2 5 1
1 1 1 1 1

4

9
13
2
5 1 7 8 5 7 1 4 1
1 2 1 1 3 3 2 1 2

4