1945번 - 직사각형

문제

2차원 평면상에 N개의 직사각형이 있다. 직사각형의 각 변은 각 좌표축과 평행하다. 이들 직사각형은 다른 직사각형와 겹쳐지거나 일치할 수 있으며, 다른 것의 내부에 그려질 수도 있다. 직사각형의 각 꼭짓점은 자연수 좌표를 가진다.

위의 그림의 경우는 8개의 직사각형이 그려진 경우이다. 이제 이 2차원 평면에 원점 (0,0)을 지나는 직선을 하나 그릴 수 있다. 이 직선은 직사각형들과 교차할 수 있는데, 위의 그림의 경우 2, 5, 6, 7, 8번 직사각형들과 교차하게 된다. (단지 직사각형의 꼭짓점만을 스쳐 지나가더라도 교차하는 것으로 간주한다.)

가장 많은 직사각형과 교차하도록 원점을 지나는 직선을 그린다고 할 때, 최대 몇 개의 직사각형과 교차할 수 있는지를 구하는 프로그램을 작성하시오. 위의 그림의 경우 직선을 어떻게 그린다고 해도 6개 이상의 직사각형과는 교차하지 않으므로, 5개가 최대가 된다.

입력

첫째 줄에 직사각형의 개수 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 직사각형의 왼쪽 아래 꼭짓점의 좌표 xbl, ybl과 오른쪽 위 꼭짓점의 좌표 xtr, ytr이 순서대로 빈칸 하나를 사이에 두고 주어진다. 입력되는 좌표는 1,000,000,000 이하의 자연수이고, xbl < xtr, ybl < ytr 을 만족한다.

출력

첫째 줄에 최대로 교차할 수 있는 직사각형의 개수를 출력한다.

제한

힌트