동아리방 보수

면접 대비

시간 제한2초메모리 제한512 MB

요약

각 방에는 클럽 하나, 각 클럽에는 방 하나를 배정하되 종빈이 비용에서 예산을 뺀 차액을 합계 X까지 부담할 때, 방을 받는 클럽 수의 최댓값을 구한다.

난이도: 보통10점 중 6점
유형: 그리디, 정렬, 투 포인터, 이분 탐색
정답자: 아직 제출이 없습니다

문제

어느 대학에 동아리방이 $N$ 개 있었다. 그런데 어느 날 나타난 빌런이 동아리방을 모두 부수고 동아리를 내쫓았다. 빌런이 떠난 자리에는 무너진 동아리방만 남았다.

동아리방을 잃은 동아리는 $M$ 개이고, $i$ 번째 동아리는 예산 $S_i$ 원이 있다. 각 동아리는 이 예산 안에서 동아리방 하나를 고쳐 쓰려고 한다. $j$ 번째 동아리방을 다시 쓰려면 보수비용 $C_j$ 원이 든다. 동아리방 하나에는 동아리 하나만 배정되고, 동아리 하나는 동아리방을 하나만 가진다. 보수하고 예산이 남아도 다른 동아리에 돈을 보태주지는 않는다.

종빈이는 동아리방이 없는 설움을 잘 알기에, 예산이 모자라 동아리방을 얻지 못하는 동아리를 도우려 한다. $i$ 번째 동아리에 $j$ 번째 동아리방을 배정하면 동아리는 자기 예산에서 최대 $S_i$ 원을 내고, 모자란 $\max(0, C_j - S_i)$ 원은 종빈이가 보탠다. 종빈이가 보태는 금액의 합은 $X$ 원을 넘을 수 없다.

동아리방을 가질 수 있는 동아리는 최대 몇 개인지 구하라.

입력

첫째 줄에 $N$ , $M$ , $X$ 가 주어진다. ( $1 \le N \le 100000$ , $1 \le M \le 100000$ , $0 \le X \le 1000000000$ )

둘째 줄에 동아리방 $N$ 개의 보수비용 $C_1, C_2, \dots, C_N$ 이 차례로 주어진다. ( $0 \le C_j \le 1000000000$ )

셋째 줄에 동아리 $M$ 개의 예산 $S_1, S_2, \dots, S_M$ 이 차례로 주어진다. ( $0 \le S_i \le 1000000000$ )

출력

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

설명

보수비용이 $5, 8, 9, 1, 7$ 이고 동아리의 예산이 $2, 10, 5, 3$ 이며 $X = 3$ 인 경우를 보자.

예산이 $10$ 인 동아리에 보수비용 $9$ 인 동아리방을, 예산이 $5$ 인 동아리에 보수비용 $5$ 인 동아리방을, 예산이 $3$ 인 동아리에 보수비용 $1$ 인 동아리방을 배정한다. 이 동아리 세 곳은 모두 자기 예산으로 보수비용을 감당하므로 종빈이가 한 푼도 보태지 않고 동아리 $3$ 개가 동아리방을 얻는다.

동아리 $4$ 개에 모두 동아리방을 주려면 종빈이가 적어도 $4$ 원을 보태야 하는데, 이는 한도인 $3$ 원을 넘으므로 불가능하다.

예제2

예제 1
입력
```
3 4 0
1 2 3
3 3 3 3
```
예상 출력
```
3
```
예제 2
입력
```
5 4 3
5 8 9 1 7
2 10 5 3
```
예상 출력
```
3
```