Problem
Một ngày nọ, như một hình phạt cho những trò chơi khăm và lừa dối, dì Polly bắt Tom sơn hàng rào sân
L. Tất cả các bạn đều nhớ rất rõ rằng Tom đã bán (với nhiều món quà khác nhau) tác phẩm của mình cho những cậu bé khác muốn quét vôi lại hàng rào.
Khi Tom hết vôi, hàng rào đã được sơn bởi
N các cậu bé. Và vì Tom không thực sự đi theo các cậu bé nên mọi người đã sơn phần hàng rào mà cậu ấy thích nhất.
Mỗi cậu bé thứ
i bắt đầu sơn hàng rào từ một tấm ván thẳng đứng có tọa độ
Tráii và sơn lên tấm ván có tọa độ
Phải< sub>i (độ dài của bàn cờ được coi là bằng 1).
Xác định chiều dài của hàng rào mà Tom sẽ phải tự sơn.
Đầu vào
Dòng đầu tiên chứa số L - chiều dài hàng rào của dì Polly. Dòng thứ hai chứa số N, các dòng tiếp theo N - cặp Trái< sub>i và Phảii. Tất cả các số đều là số nguyên
Hạn chế:
\(0 <= L <= 2 \cdot 10^9\);
\(-10^9 <= Left_i <= Right_i <= 10^9\);
\(1 <= N <= 15 000\).
Dấu ấn
In ra một số - chiều dài của hàng rào mà Tom cần sơn xong.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
20
1
10 20
|
10 |
| 2 |
10
1
10 10
| 10 |
| 3 |
100
2
10 30
20 40
| 70 |