Minimum Chunks Required (Akuna Shang Hai )

A file contains totalPackets packets numbered 1-based. The uploaded ranges do not overlap; each contiguous range not yet uploaded can be split into any number of contiguous chunks, where each chunk length must be a non-negative integer power of 2, and the chunk start does not need to be aligned to its length. Find the minimum number of chunks still to be uploaded.

输入格式

The first line contains totalPackets and m; each of the next m lines contains an uploaded closed range l r. Original limits: 1≤totalPackets<10^18, 0≤m<10^5, 1≤l≤r≤totalPackets, and the ranges do not overlap.

输出格式

Output the minimum number of chunks that must be uploaded.

样例 1

输入：

10 2
1 2
9 10

输出：

2

样例 2

输入：

18 1
9 17

输出：

2

样例 3

输入：

1 0

输出：

1