Hình hộp và vòi nước

Một bể kính hình hộp chữ nhật có bề rộng \(1\) cm, chiều dài \(m\) cm và chiều cao lớn vô hạn. Đáy bể được chia thành \(m\) ô vuông \(1 \times 1\) cm, đánh số từ \(1\) đến \(m\) theo chiều từ trái sang phải.

Trong bể có \(n\) cột đá hình hộp, cột thứ \(i\) nằm trọn trong ô \(p_i\) (chiếm hết đáy ô đó, kích thước đáy \(1 \times 1\) cm) và cao \(x_i\) cm. Các cột nằm ở các ô khác nhau và \(p_1 < p_2 < \dots < p_n\). Cột đá không thấm nước và chiếm chỗ, nên phần thể tích của ô bị cột choán không chứa nước.

Một vòi nước đặt ngay ở ô \(1\), mỗi giây chảy ra đúng \(1\) cm\(^3\) nước. Nước chảy tràn tự nhiên: nó dồn xuống chỗ thấp, bị chặn bởi thành bể ở hai đầu và bởi các cột đá, tràn qua đỉnh cột khi mực nước vượt độ cao của cột.

Một cột đá \(i\) được xem là đã chìm khi mặt nước ở mọi ô kề với nó (ô \(p_i-1\) và ô \(p_i+1\), nếu các ô đó nằm trong bể) đạt độ cao từ \(x_i\) trở lên.

Hãy tính số giây nhỏ nhất để tất cả \(n\) cột đá đều đã chìm.

Input

• Dòng đầu chứa hai số nguyên \(n\) và \(m\).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(p_i\) và \(x_i\).

Output

In ra một số nguyên duy nhất: số giây nhỏ nhất cần tìm.

Constraints

• \(1 \le n \le 10^5\), \(1 \le m \le 10^9\), \(n \le m\).
• \(1 \le p_1 < p_2 < \dots < p_n \le m\).
• \(1 \le x_i \le 10^9\).
• Subtask 1 (50%): \(n = 1\). Subtask 2 (50%): không có ràng buộc thêm.

Sample Input

3 6
2 2
4 3
5 1

Sample Output

12

Explanation

Cột cao nhất cao \(3\) cm nên cuối cùng mặt nước phải cao \(3\) cm trên toàn bể: \(6\) ô ứng với \(6 \times 3 = 18\) cm\(^3\), trừ đi phần các cột choán chỗ (\(2 + 3 + 1 = 6\) cm\(^3\)), còn \(12\) cm\(^3\) nước, tức \(12\) giây.