시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 55 28 24 51.064%

문제

아주대학교에는 N개의 동아리방이 있었다. 빅-종빈빌런이 나타나기 전까지는. 어느날 나타난 빅-종빈빌런은 아주대학교의 모든 동아리방을 파괴하고, 동아리들을 내쫓았다. 빅-종빈빌런이 떠난 자리에는 무너져내린 동방만이 남았다.

M 개의 동방 없는 동아리들은 각자 Si (1 ≤ i ≤ M)만큼의 예산을 가지고 있다. 각 동아리는 최대 이 예산을 사용하여 동아리방을 재건하려고 한다. 각 동방을 다시 사용할 수 있기 위해서는 보수비용으로 Ci (1 ≤ Ci ≤ N)원이 필요하다. 한 동방은 하나의 동아리에 배정될 수 있으며, 하나의 동아리는 하나의 동방만을 가질 수 있다. 각 동아리는 보수를 하고 돈이 남는다고 해서 다른 동아리에 돈을 보태주지는 않는다.

종빈이는 소속된 소학회가 동방이 없어 동방 없는 동아리가 얼마나 서러운지 잘 안다. 이에 최대한 많은 동아리가 동방을 가질 수 있게 도와주려 한다. 종빈이가 도울 것은 당연히 예산이 부족해 동아리방을 얻지 못하는 동아리들이다. 종빈이는 이러한 동아리들에게 동방 보수 비용을 보태주려고 한다. 

종빈이가 도와줄 수 있는 금액의 합계가 최대 X원이라고 할 때, 동방을 가질 수 있는 동아리는 최대 몇 개일지를 알아보자.

입력

첫 줄에 N (1 ≤ N ≤ 100,000), M (1 ≤ M ≤ 100,000), X (0 ≤ X ≤ 1,000,000,000) 가 주어진다. 두 번째 줄에 N개의 동방 보수비용 Ci (0 ≤ Ci ≤ 1,000,000,000)가 차례로 주어진다. 세 번째 줄에 M개의 동아리의 예산 Si (0 ≤ Si ≤ 1,000,000,000) 가 차례로 주어진다.

출력

동방을 가질 수 있는 동아리의 최대 개수를 한 줄에 출력한다.

예제 입력 1

3 4 0
1 2 3
3 3 3 3

예제 출력 1

3

예제 입력 2

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

예제 출력 2

3

힌트

2번 예제에서 각 동아리방을 고치는데 비용이 5, 8, 9, 1, 7이고 각 동아리 들은 2, 10, 5, 3의 금액을 가지고 있다. 

이때 2번 동아리에 3번방, 4번 동아리에 4번방 배정하면 종빈이가 돈을 지원해 줄 필요가 없고3번동아리에 1번방을 배정하면 종빈이가 2원을 지원해주면서 종빈이의 도와줄 수 있는 금액 한도 내에서 3개의 동아리가 동아리방을 배정받을 수 있게 된다.

어떻게 배정해도 4개의 동아리가 모두 방을 배정받을 순 없다.

출처

University > 경인지역 6개대학 연합 프로그래밍 경시대회 > shake! 2017 C번

  • 문제를 만든 사람: Acka
  • 문제의 오타를 찾은 사람: didgogns