당신은 마트료시카 인형을 판매하는 가게를 열기로 했다. 당신은 N개의 마트료시카 인형을 공장에 주문했다. 여기에는 1부터 N까지의 번호가 붙어 있었다. 그 중 i번째(1 ≤ i ≤ N) 마트료시카 인형은 바닥의 지름이 Ricm, 높이가 Hi cm인 속이 빈 원기둥으로 생각 할 수 있다. 마트료시카 인형은 중첩해서 안에 넣을 수 있다. 각각의 마트료시카 인형은, 자신보다 지름과 높이가 모두 작은 마트료시카 인형을 1개까지만 안에 넣을 수 있다. 수납된 마트료시카 인형 안에 다른 인형을 넣을 수도 있다.

어느 날, 마트료시카 인형을 주문한 공장에서 연락이 왔다. 주문한 N개의 마트료시카 인형을 모두 한번에 준비 할 수 없어서, N개의 마트료시카 인형 중 바닥의 직경이 A cm 이상, 높이 B cm 이하의 마트료시카만 모두 사전에 보내준다고 한다. A와 B는 갑자기 변할지도 모른다. 그래서 당신은, Q개의 쌍 (Aj , Bj ) (1 ≤ j ≤ Q) 각각에 대해, 사전에 도착하는 마트료시카 인형을 중첩해서 넣었을 때, 어떤 마트료시카 인형에도 들어가지 못하는 인형의 갯수의 최솟값을 구하기로 하였다.

각각의 마트료시카 인형의 바닥의 지름과 높이에 대한 정보와, Q개의 쌍 (Aj , Bj ) (1 ≤ j ≤ Q)이 주어진다.

각각의 쌍에 대해서, 사전에 도착하는 마트료시카 인형을 중첩해서 넣을 때, 어떤 마트료시카 인형에도 들어가지 못하는 마트료시카 인형의 갯수의 최솟값을 구하는 프로그램을 작성하여라.

• 1 ≤ N ≤ 200 000

• 1 ≤ Q ≤ 200 000

• 1 ≤ Ri ≤ 1 000 000 000 (1 ≤ i ≤ N)

• 1 ≤ Hi ≤ 1 000 000 000 (1 ≤ i ≤ N)

• 1 ≤ Aj ≤ 1 000 000 000 (1 ≤ j ≤ Q)

• 1 ≤ Bj ≤ 1 000 000 000 (1 ≤ j ≤ Q)

#5031 upload 6 done 3 how_to_reg 3 call_split Subtarea

마트료시카 timer 2s memory 512MB

#5031
Subtarea

마트료시카 2s 512MB