충전 단위 나누기

문제

도심 공유 자전거 서비스의 하루 운영 계획을 세운다. 오늘 들어온 이용 요청은 N건이며, i번째 요청은 d_i km를 한 번에 달려야 한다. 대여소에는 자전거가 M대 있고, j번째 자전거는 추가로 충전하지 않으면 최대 r_j km까지 달릴 수 있다. 하나의 요청에는 자전거를 한 대만 배정할 수 있고, 한 자전거는 하루에 최대 한 건의 요청만 처리한다. 요청 i를 배정받은 자전거의 주행 가능 거리는 d_i 이상이어야 한다. 운영팀에는 충전 단위가 P개 있다. 충전 단위 하나를 자전거 한 대에 쓰면 그 자전거의 주행 가능 거리가 정확히 1 km 늘어난다. 한 자전거에 여러 단위를 쓸 수 있고, 단위는 쪼갤 수 없으며, P개를 모두 쓸 필요는 없다. 충전 단위를 어떻게 나누어 쓸지, 어떤 요청을 어떤 자전거에 배정할지는 모두 운영팀이 자유롭게 정한다. 배정받지 못한 요청은 취소된다. 충전 단위를 알맞게 사용해 처리할 수 있는 요청의 수를 최대로 만들려 한다. 처리할 수 있는 요청의 최대 개수를 구하시오. 하나도 처리할 수 없으면 0을 출력한다.

입력

첫 줄에 정수 N, M, P가 공백으로 구분되어 주어진다. (1 ≤ N, M ≤ 200,000, 0 ≤ P ≤ 10^15) 둘째 줄에 d_1, ..., d_N이, 셋째 줄에 r_1, ..., r_M이 공백으로 구분되어 주어진다. (1 ≤ d_i, r_j ≤ 10^9, 모두 정수)

출력

처리할 수 있는 요청의 최대 개수를 한 줄에 출력한다.

4 3 5
3 8 5 10
4 2 6

3

3 3 2
10 9 8
1 1 1

0

2 2 0
5 5
5 7

2

출처: Devin.KR 자체 제작