Photo
You are given a photo of the skyline of Târgu-Mures taken during the night. Some rooms still have the light on. You know that all the buildings can be modeled by rectangles of surface area at most A. Find the minimum number of buildings that can lead to the picture.
Specifically, you are given an integer A, and N points at integer coordinates (x,y). You must find a minimum number of rectangles that have one side on the x-axis and area at most A, which cover all points. The rectangles may overlap.
InputThe first line will contain two integers N and A, separated by a single space. The next N lines will contain two integers x and y, representing the coordinates of each point.
OutputThe output should consist of exactly one line containing the minimum number of rectangles.
1 ≤ N ≤ 100
1 ≤ A ≤ 200 000
Each point has 0 ≤ x ≤ 3 000 000 and 1 ≤ y ≤ A
Input:
Output:
6 4
2 1
4 1
5 1
5 4
7 1
6 4Output:
3Here is one possible picture that explains the example:
Image: explain1
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.