저녁 피카

Sara는 피카를 정말 좋아한다! Sara는 저녁 피카를 사라고 엄마에게 방금 스웨덴 크로나 $P$를 받았다. Sara는 영리하므로, 돈을 최대한 현명하게 쓰려고 한다. Lugnbyrån 상점에는 구매할 수 있는 페이스트리가 $N$개 있다. 각 페이스트리에는 정해진 가격과 특정 범주가 있다. Sara는 피카를 매우 좋아하기 때문에, 거의 모든 종류의 페이스트리가 똑같이 맛있다고 생각한다. 즉, 어떤 범주의 페이스트리를 살지에는 선호가 없지만, 같은 범주의 페이스트리를 $K$개보다 많이 사면 조금 지나치게 단조로울 것이라고 느낀다.

Sara가 총비용이 $P$ 이하가 되도록 최대한 많은 페이스트리를 사게 도와주자. 또한, 구매한 페이스트리 중 같은 범주에 속한 것이 $K$개를 넘지 않도록 해야 한다. 어떤 것을 사는지가 아니라, 살 수 있는 페이스트리의 개수만 출력하면 된다.

채점

해결책은 각각 일정한 점수가 배정된 여러 테스트 그룹에서 평가된다. 각 테스트 그룹에는 여러 테스트 케이스가 포함된다. 한 테스트 그룹의 점수를 얻으려면 그 테스트 그룹의 모든 테스트 케이스를 해결해야 한다.

그룹 | 점수 | 제약 조건

$1$ |$20$| 이 하위 문제에는 포스터에 있는 테스트 케이스(https://www.progolymp.se/2025/affisch.pdf) 하나만 있다.

$2$ |$5$| $K=N$이고 모든 페이스트리를 하나도 빠짐없이 살 수 있다.

$3$ |$15$| 모든 페이스트리를 하나도 빠짐없이 살 수 있다.

$4$ |$5$| $c_i=1$, 즉 모든 페이스트리의 가격은 $1$크로나이다.

$5$ |$17$| $K=N, N \leq 500$

$6$ |$21$| $K=N$

$7$ |$9$| $N \leq 500$

$8$ |$8$| 추가 제약 조건이 없다.

입력의 첫째 줄에는 Sara가 고를 수 있는 페이스트리의 개수를 나타내는 정수 $N$ ($1 \leq N \leq 10^5$)가 주어진다.

다음 줄에는 Sara가 저녁 피카 예산으로 가진 크로나의 수를 나타내는 정수 $P$ ($1 \leq P \leq 10^8$)가 주어진다.

다음 줄에는 Sara가 각 범주에서 먹을 의향이 있는 페이스트리의 최대 개수를 나타내는 정수 $K$ ($1 \leq K \leq N$)가 주어진다.

다음 줄에는 정수 $c_1, c_2, \dots, c_N$ ($1 \leq c_i \leq P$)가 주어진다. 여기서 $c_i$는 페이스트리 $i$의 가격이 $c_i$크로나임을 의미한다. 모든 페이스트리의 총비용이 반드시 32비트 정수에 들어맞는 것은 아님에 유의하라.

마지막 줄에는 정수 $t_1, t_2, \dots, t_N$ ($1 \leq t_i \leq 10^5$)가 주어진다. 페이스트리의 범주는 정확히 $10^5$개이며, 각 범주는 정수로 지칭한다. 각 $t_i$는 페이스트리 $i$가 범주 $t_i$에 속함을 의미한다.

Sara가 예산을 최적으로 사용할 때 살 수 있는 페이스트리의 개수를 정수로 출력한다.

이 예제에서 Sara는 모든 페이스트리를 살 수 있지만, 모두 같은 범주(범주 1)에 속한다. 범주마다 최대 2개를 살 수 있으므로, 그중 2개를 구매할 수 있다.

이 예제에서는 $K$가 크므로 범주는 문제가 되지 않지만, Sara는 모든 페이스트리를 살 수 없다. 가격이 $4, 3, 2, 1$인 페이스트리들을 사면 정확히 4개를 살 수 있다.

최적해는 가격이 $1, 1, 4, 5$인 페이스트리들을 사는 것이다. 여기서 범주에 따른 제한이 없었다면 Sara는 페이스트리를 더 많이 살 수 있었을 것이다.