도서실 카펫

직사각형 도서실 바닥에 여러 개의 직사각형 얼룩이 있다. 얼룩들은 서로 겹치지 않지만 맞닿을 수는 있고, 모든 얼룩의 변은 도서실 벽과 평행하다.

한 변의 길이가 정해진 정사각형 카펫 한 장을 도서실 벽과 평행하게 놓으려고 한다. 카펫은 도서실 안에 완전히 들어가야 한다. 어떤 얼룩의 직사각형 전체가 카펫 안에 포함될 때 그 얼룩을 가렸다고 한다.

카펫의 위치를 적절히 정했을 때 완전히 가릴 수 있는 얼룩의 최대 개수를 구하시오.

모든 직사각형의 좌표는 1,000,000보다 작은 음이 아닌 정수이고, 가로와 세로의 길이는 1,000,000보다 작은 양의 정수이다. 얼룩 직사각형들은 서로 겹치지 않지만 맞닿을 수 있다. 얼룩 직사각형과 가능한 카펫 배치는 모두 도서실 직사각형 안에 완전히 포함된다. 얼룩 직사각형의 수는 최대 100,000개이다.

첫째 줄에는 도서실 직사각형의 왼쪽 위 꼭짓점과 오른쪽 아래 꼭짓점의 좌표가 주어진다.

둘째 줄에는 정사각형 카펫의 한 변의 길이가 주어진다.

셋째 줄에는 얼룩의 수가 주어진다.

이후 각 줄에는 얼룩 직사각형 하나의 왼쪽 위 꼭짓점과 오른쪽 아래 꼭짓점의 좌표가 주어진다.

정사각형 카펫 한 장으로 완전히 가릴 수 있는 얼룩의 최대 개수를 출력한다.