만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

프롬

면접 대비

시간 제한1초메모리 제한128 MB

요약
키 차이가 k 이하인 여학생과 남학생 쌍의 개수를 구합니다.
난이도

보통10점 중 4점

유형
정렬, 투 포인터, 이분 탐색
정답자
아직 제출이 없습니다

문제

조니는 전통적으로 폴로네이즈 춤으로 시작하는 프롬을 준비하고 있다. 남녀 한 쌍이면 누구든 폴로네이즈를 이끌 수 있으며, 두 사람의 키 차이가 kk 바이트미터를 넘지 않아야 한다. 지미는 폴로네이즈를 이끌 수 있는 쌍이 몇 가지인지 알고 싶어 한다.

입력

첫 줄에 세 정수 nn, mm, kk가 공백으로 구분되어 주어진다 (1≤n,m≤2500001 \le n, m \le 250000, 0≤k≤10000000000 \le k \le 1000000000). 각각 여학생 수, 남학생 수, 허용되는 키 차이의 최댓값이다. 둘째 줄에는 여학생 nn명의 키 aia_i (1≤ai≤10000000001 \le a_i \le 1000000000)가, 셋째 줄에는 남학생 mm명의 키 bib_i (1≤bi≤10000000001 \le b_i \le 1000000000)가 공백으로 구분되어 주어진다. 키의 단위는 바이트미터다.

출력

이끌 수 있는 쌍의 개수를 정수 하나로 출력한다.

힌트

이끌 수 있는 쌍은 11가지다: (15,10), (15,15), (1,1), (1,5), (1,1), (5,1), (5,5), (5,10), (5,1), (7,5), (7,10).

예제1

  1. 예제 1

    입력
    4 5 5
    15 2 5 7
    1 5 10 15 1
    
    예상 출력
    11