Bạn đang tham gia một cuộc thi đi xuyên Ai Cập từ tây sang đông dọc theo một đoạn thẳng. Ban đầu, bạn ở đầu mút phía tây của đoạn thẳng. Quy tắc của cuộc thi yêu cầu bạn luôn di chuyển dọc theo đoạn thẳng và luôn đi về phía đông.

Trên đoạn thẳng có \(N\) thiết bị dịch chuyển tức thời. Mỗi thiết bị có hai đầu mút. Mỗi khi bạn đi tới một đầu mút của thiết bị, thiết bị lập tức đưa bạn tới đầu mút còn lại. Tùy vào đầu mút mà bạn gặp, lần dịch chuyển này có thể đưa bạn về phía đông hoặc phía tây so với vị trí hiện tại. Sau khi được dịch chuyển, bạn phải tiếp tục đi về phía đông dọc theo đoạn thẳng; bạn không thể tránh bất kỳ đầu mút nào nằm trên đường đi của mình. Không có hai đầu mút của các thiết bị ở cùng một vị trí. Mọi đầu mút đều nằm hẳn bên trong đoạn thẳng, không trùng với điểm bắt đầu hoặc điểm kết thúc.

Mỗi lần được dịch chuyển, bạn nhận được \(1\) điểm. Mục tiêu của cuộc thi là kiếm được nhiều điểm nhất có thể. Để tăng số điểm, bạn được phép thêm tối đa \(M\) thiết bị mới vào đoạn thẳng trước khi bắt đầu hành trình. Bạn cũng được tính điểm khi sử dụng các thiết bị mới.

Bạn có thể đặt các đầu mút của thiết bị mới ở bất kỳ vị trí nào, kể cả vị trí có tọa độ không nguyên, miễn là không trùng với vị trí của một đầu mút khác. Nói cách khác, vị trí của tất cả các đầu mút, thuộc cả thiết bị cũ lẫn thiết bị mới, phải đôi một khác nhau. Các đầu mút mới cũng phải nằm hẳn giữa điểm bắt đầu và điểm kết thúc của đoạn thẳng.

Dữ liệu bảo đảm rằng dù bạn thêm các thiết bị như thế nào theo các quy tắc trên, bạn vẫn luôn có thể đi tới điểm kết thúc của đoạn thẳng.

Cho vị trí các đầu mút của \(N\) thiết bị ban đầu và số thiết bị mới tối đa \(M\) mà bạn được thêm, hãy viết chương trình tính số điểm lớn nhất bạn có thể kiếm được.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng thứ nhất chứa số nguyên \(N\), là số thiết bị dịch chuyển ban đầu trên đoạn thẳng.
• Dòng thứ hai chứa số nguyên \(M\), là số thiết bị mới tối đa mà bạn được thêm.
• Mỗi dòng trong \(N\) dòng tiếp theo mô tả một thiết bị. Dòng thứ \(i\) trong số này mô tả thiết bị thứ \(i\), chứa hai số nguyên \(W_i\) và \(E_i\), cách nhau bởi một dấu cách. Hai số này lần lượt là khoảng cách từ điểm bắt đầu của đoạn thẳng tới đầu mút phía tây và đầu mút phía đông của thiết bị.

Không có hai đầu mút nào của các thiết bị cho trước có cùng vị trí. Đoạn thẳng mà bạn đi trên đó bắt đầu tại vị trí \(0\) và kết thúc tại vị trí \(2\,000\,001\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên: số điểm lớn nhất bạn có thể kiếm được.

Ràng buộc

• \(1 \le N \le 1\,000\,000\): số thiết bị ban đầu trên đoạn thẳng.
• \(1 \le M \le 1\,000\,000\): số thiết bị mới tối đa được thêm.
• \(1 \le W_i < E_i \le 2\,000\,000\) với \(1 \le i \le N\): khoảng cách từ điểm bắt đầu tới đầu mút phía tây và đầu mút phía đông của thiết bị thứ \(i\).

Chấm điểm trên hệ thống

Lưu ý: Cách chia nhóm và tính điểm dưới đây là bản điều chỉnh để luyện tập trên hệ thống, không khẳng định tương đương cách chấm tại IOI gốc.

Mỗi nhóm được chấm độc lập: chỉ nhận điểm của nhóm khi vượt qua tất cả bộ kiểm thử trong nhóm; nếu có bộ kiểm thử không đạt thì nhóm nhận 0 điểm. Tổng điểm tối đa là 100.

Nhãn nhóm là phần số trong tên tệp dữ liệu gốc. Tất cả tệp cùng nhãn, kể cả các hậu tố chữ và pf, đều thuộc nhóm đó.

Các ví dụ trong đề không tính điểm. Các tệp ví dụ gốc có nhãn 0 được giữ lại riêng và có trọng số 0.

Tệp ví dụ gốc: tel/tel0a.in, tel/tel0b.in.

Ví dụ

3
1
10 11
1 4
2 3

6

3
3
5 7
6 10
1999999 2000000

12

Nguồn

IOI 2008, ngày thi thứ hai: Teleporters, bản tiếng Anh 1.2. Tác giả đề bài: Masaki Watanabe (Nhật Bản). Tập đề bài và lời giải IOI 2008.