루미 알고리즘

#1622실버Evening Fika

PO 2025 온라인 예선코딩출제 Joshua Andersson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Sara loves fika! She has just received P Swedish kronor from her mom to buy some evening fika. Since Sara is smart, she will try to spend the money as wisely as possible. At the store Lugnbyrån, there are N pastries available. Each pastry has a certain price and a specific category. Because Sara likes fika so much, she almost thinks all kinds of pastries are equally tasty. Namely, she has no preference for which category of pastry to buy, but she feels it would be a bit too monotonous if she buys more than K pastries of the same category.

Help Sara buy as many pastries as possible, with a total cost less than or equal to P. Also, ensure that there are no more than K pastries from the same category among those she bought. You only need to print out how many pastries she can buy, not which ones.

Input

The first line of the input contains the integer N (1 ≤ N ≤ 10^5), the number of pastries Sara can choose from.

The next line contains the integer P (1 ≤ P ≤ 10^8), the number of kronor Sara has as a budget for her evening fika.

The next line contains the integer K (1 ≤ K ≤ N), the maximum number of pastries from each category that Sara is willing to eat.

The next line contains the integers c_1, c_2, …, c_N (1 ≤ c_i ≤ P), where c_i means that that pastry i costs c_i kronor. Note that the total cost of all pastries may not necessarily fit in a 32-bit integer.

The last line contains the integers t_1, t_2, …, t_N (1 ≤ t_i ≤ 10^5). There are exactly 10^5 categories of pastries, and we refer to each with an integer. Each t_i means that that pastry i belongs to category t_i.

Output

Print an integer: the number of pastries that Sara can buy if she uses her budget optimally.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

GroupPointsConstraints
120The subtask has a single testcase, the one on the poster (https://www.progolymp.se/2025/affisch.pdf).
25K=N and you can afford to buy every single pastry.
315You can afford to buy every single pastry.
45c_i=1, that is to say every pastry costs 1 krona.
517K=N, N ≤ 500
621K=N
79N ≤ 500
88No additional constraints.

Explanation of Sample 1

In this sample, Sara can afford to buy all the pastries, but they all belong to the same category (category 1). Since she can buy at most 2 per category, she can purchase 2 of them.

Explanation of Sample 2

In this sample, categories are not a problem because K is large, but Sara cannot afford to buy all the pastries. If she buys the pastries priced at 4, 3, 2, 1, she can afford exactly 4.

Explanation of Sample 3

An optimal solution is to buy pastries priced at 1, 1, 4, 5. Here, Sara could have bought more pastries if not limited by the categories.

예제

예제 1

입력
3
10
2
2 3 2
1 1 1
출력
2

예제 2

입력
5
10
5
4 3 2 5 1
1 1 1 1 1
출력
4

예제 3

입력
9
13
2
5 1 7 8 5 7 1 4 1
1 2 1 1 3 3 2 1 2
출력
4

출처 표기

출처: Programmeringsolympiaden 2025년 온라인 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.