[CEOI2009Day1] photo

内存限制：256 MB 时间限制：1000 ms

You are given a photo of the skyline of Târgu-Mureş 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.

The first line of the input 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.

The output should consist of exactly one line containing the minimum number of rectangles.

样例输入 1

样例输出 1

Here is one possible picture that explains the example:

Constraints

$1 ≤ N ≤100$
$1 ≤ A ≤ 200 000$
Each point has $0 ≤ x ≤ 3 000 000$ and $1 ≤ y ≤ A$
For 30% of thetest cases, $1 ≤ N ≤ 18$

C0520 [CEOI2009Day1] photo

题目描述

输入格式

输出

样例

样例输入 1

样例输出 1

提示