АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

FJ wants to take pictures of his N cows (2 <= N <= 1,000,000,000), which are standing in a line and conveniently numbered 1..N. Each photograph can capture a consecutive range of cows from the lineup, and FJ wants to make sure that each cow appears in at least one photo. Unfortunately, there are K unfriendly pairs of cows (1 <= K <= 1000) that each refuse to be in the same photograph. Given the locations of these unfriendly pairs, please determine the minimum number of photos FJ needs to take.

Input

Input description...

Output

Output description...

Example

Input:
etc.

Output:
etc.