Băng chuyền có N vị trí xếp vòng tròn (0..N-1). Có M hành lý, hành lý thứ i ban đầu ở vị trí P[i] và cần được lấy ra tại vị trí Q[i]. Mỗi giây băng chuyền quay 1 bước (vị trí v → v+1 mod N). Hành lý được lấy khi tới đúng vị trí Q[i]. In tổng số giây cần thiết để lấy hết tất cả hành lý (giây mà hành lý cuối cùng được lấy).
Dòng 1: N và M. M dòng tiếp theo, mỗi dòng có P[i] và Q[i].
1 <= N <= 10^9; 1 <= M <= 10^5; 0 <= P[i], Q[i] < N
Tổng số giây.
Ví dụ:
Đầu vào:
10 3
0 5
2 7
8 1
Đầu ra:
5
Giải thích:
Đang tải editor...