Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P165SUMJ - ROUND 5J - Học hè

OOO đang định quay lại trường để học thêm các khóa học mùa hè, cậu định ra trường sớm. Nhà trường mở ra n môn học, môn học bắt đầu từ ngày st[i] đến ngày en[i] và diễn ra liên tục không nghỉ ngày nào. Tuy nhiên, mùa hè Hà Nội lại quá nóng nên cậu đang băn khoăn không biết sẽ lên Hà Nội vào ngày nào và về ngày nào. OOO có Q kế hoạch cho ngày đi và ngày về, các bạn hãy thử tính giúp xem, với mỗi kế hoạch thì OOO sẽ học được nhiều nhất bao nhiêu môn học để cậu có thể sớm ra trường nhé. Ngoài ra, để có thể học tốt, OOO sẽ không học một lúc 2 môn học, cụ thể hơn, OOO không thể học 2 môn học trong cùng một ngày, và khi học một môn học cậu phải đi học đầy đủ, không bỏ buổi nào.

 

Input

Dòng đầu tiên chứa 2 số nguyên n và Q lần lượt là số môn học trong hè và số dự định thời gian lên Hà Nội của OOO (1 <= n, Q <= 10^5)

Dòng thứ i trong n dòng tiếp theo gồm 2 số nguyên st và en thể hiện cho ngày bắt đầu và ngày kết thúc của môn học thứ i (1 <= st <= en <= 10^6)

Dòng thứ I trong Q dòng tiếp theo chứa 2 số nguyên a và b thể hiện cho ngày OOO lên Hà Nội và ngày OOO về quê (1 <= a <= b <= 10^6)

Output

Gồm Q dòng, mỗi dòng ghi số lượng môn học nhiều nhất mà OOO có thể học được.

Example

Input:
3 1
3 9
7 10
15 17
1 20 Output: 2

Được gửi lên bởi:Admin
Ngày:2016-08-05
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.