题目描述

The city's art museum is known for its long straight corridor and the artistically decorated tiles laid along it. The corridor is a rectangular area 2 meters wide and is divided into one-meter-square cells. Each cell is either occupied by a single tile or is empty.

As a part of the renovation of the museum, all the empty cells will be covered with tatami mats, which are traditional Japanese floor mats. Each tatami mat is 1 meter by 2 meters in size, so each tatami mat covers exactly two adjacent cells. Tatami mats must not overlap each other, and they must not overlap any tile.

Depending on the initial placement of the tiles, it may be impossible to cover all the empty cells with tatami mats. To address this, the museum allows each tile to be moved from its original position to one of its adjacent cells that shares a side, but not farther. Tiles must not be moved out of the corridor. No more than one tile should be on a single cell after the moves.

:::align{center}

Figure A.1. Before and after the renovation for Sample Input 1 :::

The left figure shows the initial positions of the tiles for Sample Input 1, and the right figure shows one possible way to move one tile and arrange tatami mats to cover all the empty cells.

Determine whether it is possible to cover all the empty cells with tatami mats when you move some (possibly none) of the tiles appropriately. If it is possible, find the minimum number of tiles to be moved.

输入格式

The input consists of a single test case of the following format.

$$n \ l$$ $$r_1 \ c_1$$ $$r_2 \ c_2$$ $$\vdots$$ $$r_n \ c_n$$

The integer $n$ ($1 \le n \le 10^5$) represents the number of the tiles in the corridor. The integer $l$ ($3 \le l \le 10^{18}$) represents the length of the corridor in meters. Each pair of integers $r_i$ and $c_i$ ($i = 1, \ldots, n$) satisfies $1 \le r_i \le 2$ and $1 \le c_i \le l$, and indicates the location of the $i$-th tile. Specifically, if the corridor is viewed as a rectangle with its height of 2 cells and width of $l$ cells, then the $i$-th tile is located at the $r_i$-th row from the top and the $c_i$-th column from the left. It is guaranteed that all tiles are initially on distinct cells.

输出格式

If you can cover all the empty cells in the corridor with zero or more tatami mats by moving some (possibly none) of the tiles appropriately, output the minimum number of tiles to be moved. Otherwise, output no.

4 5
2 3
1 4
1 5
2 1

1

1 3
1 1

no

6 1000000000000
1 2
1 3
1 4
2 1
2 2
2 3

3

提示

翻译由 DeepSeek V3 完成